当前位置：首页 > news >正文

力扣hot100刷题笔记——动态规划类型

news 来源：原创 2023/3/27 21:10:44

动态规划对我来说是个新名词，以前基本上没有接触过这方面的概念，查找了一些相关的资料：
1.告别动态规划，连刷 40 道题，我总结了这些套路，看不懂你打我（万字长文）
2.Dynamic Programming Patterns
3.DP IS EASY! 5 Steps to Think Through DP Questions.

总结一下相关概念：
1.动态规划是使用以前的历史记录来得出结果，避免重复计算，类似于数学归纳法，知道n=0，1和n-1的值后，利用n-1的值推导出n的结果。它和递归的不同之处在于，递归有很多重复的计算，例如在计算第n个斐波那契数列F(n)的时候，F(n) = F(n - 1) + F(n - 2)，如果是递归的话，我们需要分别计算F(n - 1)和F(n - 2)的值。但实际上在计算F(n - 1)的时候我们还会再计算一次F(n - 2)的值，如果能将F(n - 2)的值（也就是所谓的状态）存起来，我们就可以节约很多的时间，所消耗的只是存储F(n - 2)的空间而已（即所谓的空间换时间）。

2.动态规划通常使用一维/二维数组来存储历史记录，下面是解题的相关步骤（使用这个步骤可以解决大部分DP的问题，包括一些简单的中等题）：
(1).确定dp[i]的具体含义；
(2).确定dp[i]之间的关系（即计算公式）；
(3).确定初始状态值。

3.看了上面第3个博客后对动态规划有了更深的理解，它脱胎于递归，只是使用额外的空间保存了一些状态来节约时间。详见494. 目标和的第三种方案。更正，这种算法原来叫做记忆化搜索，只是对递归的剪枝并不是动态规划。

动态规划类型题目

5.最长回文子串
题目概述：给你一个字符串 s，找到 s 中最长的回文子串。
这个题目没有弄懂，还有动态规划，以后有空看看。

class Solution {private String curRes = "";public String longestPalindrome(String s) {/* 1.第一种方案双重遍历，查找最长回文字符串怎样判断？检查正反两个字符串是否相等最后超时了*/int length = s.length();String res = "";if (length < 2) {return s;}for (int i = 0; i < length; i++) {String temp = "";for (int j = i; j < length; j++) {temp += s.charAt(j);if (checkIfRevString(temp)) {if (temp.length() > res.length()) {res = temp;}}}}return res;/* 2.第二种方案，参考的题解使用双指针，从字符串的中间向两边遍历，判断是否是回文字符串同时记录当前最长的回文字符串*/this.curRes = s.substring(0, 1);for (int i = 0; i < s.length(); i++) {checkLongestPalindrome(s, i, i); // 检查奇数的情况checkLongestPalindrome(s, i, i + 1); // 检查偶数的情况}return this.curRes;/* 3.第三种方案，参考的题解使用动态规划dp[i][j] 表示s从i到j的字串是否是回文字符串dp[i][j] = dp[i + 1][j - 1] && s[i] == s[j]dp[i][i] = true;*/int length =  s.length();boolean[][] dp = new boolean[length][length];int resI = 0;int resJ = 0;for (int i = length - 1; i >= 0; i--) {for (int j = i; j < length; j++) {if (i == j) {dp[i][j] = true;} else if (j - i == 1) {dp[i][j] = s.charAt(i) == s.charAt(j) ? true : false;} else {dp[i][j] = dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j);}if (dp[i][j]) {if (j - i > resJ - resI) {resI = i;resJ = j;}}}}return s.substring(resI, resJ + 1);}public void checkLongestPalindrome(String s, int i, int j) {while (i >= 0 && j < s.length()) {if (s.charAt(i) == s.charAt(j)) {this.curRes = this.curRes.length() < j - i + 1 ? s.substring(i, j + 1) : this.curRes;i--;j++;} else {return;}}return;}private boolean checkIfRevString(String s) {StringBuilder origin = new StringBuilder(s);return origin.toString().contentEquals(origin.reverse());}
}

70. 爬楼梯
题目概述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {public int climbStairs(int n) {/* 1.第一种方案，使用递归来做，超出时间限制了*/// if (n <= 3) {//     return n;// } else {//     return climbStairs(n - 1) + climbStairs(n - 2);// }/* 2.第二种方案，参考的网上的博客，使用动态规划来做（一般用一维/二维数组完成）三个步骤：1.确定数组中每个元素的含义2.确定各个元素之间的关系（公式）3.确定初始值*/if (n <= 3) {return n;}int[] dp = new int[n];dp[0] = 0;dp[1] = 1;dp[2] = 2;for (int i = 3; i < n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n - 1] + dp[n - 2];}
}

64. 最小路径和
题目概述：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。

class Solution {public int minPathSum(int[][] grid) {/* 1.使用动态规划来完成dp[i][j] 表示到达这一格时最小的数字总和dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]; // 注意边界dp[0][0] = grid[0][0];dp[0][1] = dp[0][0] + grid[0][1];dp[1][0] = dp[0][0] + grid[1][0];*/int row = grid.length;int col = grid[0].length;int[][] dp = new int[row][col];for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {if (i == 0 && j == 0) {dp[0][0] = grid[0][0];} else if (i == 0) {dp[i][j] = dp[i][j - 1] + grid[i][j];} else if (j == 0) {dp[i][j] = dp[i - 1][j] + grid[i][j];} else {dp[i][j] = Math.min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];}}}return dp[row - 1][col - 1];}
}

322. 零钱兑换
题目概述：给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

class Solution {public int coinChange(int[] coins, int amount) {/* 1.使用动态规划解决dp[i]表示凑成总金额i所需的最少硬币个数dp[i] = min(dp[i - coins[0]], dp[i - coins[1]], ...) + 1 //注意-1表示凑不到dp[0] = 0;dp[1] = 1 or 0;*/int length = coins.length;int[] dp = new int[amount + 1];dp[0] = 0;for (int i = 1; i < amount + 1; i++) {int temp = Integer.MAX_VALUE;for (int j = 0; j < coins.length; j++) {int prevIdx = i - coins[j];if (prevIdx >= 0 && dp[prevIdx] != -1) {temp = temp < dp[prevIdx] ? temp : dp[prevIdx];}}dp[i] = temp != Integer.MAX_VALUE ? temp + 1 : -1;}return dp[amount];}
}

221. 最大正方形
题目概述：在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。

class Solution {public int maximalSquare(char[][] matrix) {/* 1.采用动态规划解题，不过这个题有点难度，思路是参考了题解才获得的dp[i][j]表示以matrix[i - 1][j - 1]为右下角的最大正方形的边长因为当前dp元素的获取需要知道上、左、左上三个dp元素的值，因而人为的在matrix的前一行/列添上0，方便计算dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;*/int row = matrix.length;int col = matrix[0].length;int[][] dp = new int[row + 1][col + 1];initArray(dp, 0);int res = 0;for (int i = 0; i < row; i++) {for (int j = 0; j < col; j++) {if (matrix[i][j] == '1') {int temp = min(dp[i][j + 1], dp[i + 1][j], dp[i][j]) + 1;dp[i + 1][j + 1] = temp;res = temp > res ? temp : res;}}}return res * res;}public void initArray(int[][] dp, int value) {Arrays.fill(dp[0], value);for (int i = 0; i < dp.length; i++) {dp[i][0] = 0;}}public int min(int a, int b, int c) {if (a > b) {return Math.min(b, c);} else {return Math.min(a, c);}}
}

279. 完全平方数
题目概述：给你一个整数n，返回和为 n 的完全平方数的最少数量。完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

class Solution {public int numSquares(int n) {/* 1.使用动态规划完成dp[i] 表示和为i的完全平方数的最少数量dp[0] = 0;dp[1] = 1;dp[2] = 2;dp[3] = 3;dp[4] = 1;dp[i] = min(dp[i - 1], dp[i - 4], dp[i - 9], ...) + 1*/int[] dp = new int[n + 1];dp[0] = 0;for (int i = 1; i < n + 1; i++) {int minValue = Integer.MAX_VALUE;for (int j = 1; i - Math.pow(j, 2) >= 0; j++) {int value = dp[i - (int)Math.pow(j, 2)];minValue = minValue < value ? minValue : value;}dp[i] = minValue + 1;}return dp[n];}
}

62. 不同路径
题目概述：一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

class Solution {public int uniquePaths(int m, int n) {/* 1.使用动态规划来实现dp[i][j]表示到达该网格不同路径的数量dp[i][j] = dp[i - 1][j] + dp[i][j - 1];dp[0][j] = 1;dp[i][0] = 1;*/int[][] dp = new int[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (i == 0) {dp[i][j] = 1;} else if (j == 0) {dp[i][j] = 1;} else {dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}}return dp[m - 1][n - 1];}
}

494. 目标和
题目概述：给你一个整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个表达式：例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

class Solution {private HashMap<Map.Entry<Integer, Integer>, Integer> state = new HashMap<>();private int[][] dp;private int absSum;public int findTargetSumWays(int[] nums, int target) {/* 1.使用递归来完成*/// int length = nums.length;// int res = 0;// if (length == 1) {//     if (0 - nums[0] == target && nums[0] == target) {//         res = 2;//     } else {//         res = (0 - nums[0] == target || nums[0] == target) ? 1 : 0;//     }// } else {//     int[] prevNums = Arrays.copyOfRange(nums, 0, length - 1);//     int lastNum = nums[length - 1];//     res = findTargetSumWays(prevNums, target - lastNum) + findTargetSumWays(prevNums, target + lastNum);// }// return res;/* 2.使用动态规划完成*/// return findTargetSumWaysHelper(nums, nums.length - 1, target, 0);/* 3.优化后的动态规划方法2中的动态规划是使用hashmap作为记忆化的组件，优化后使用数组，空间更多但访问速度更快了*/initArray(nums);return findTargetSumWaysHelperOpti(nums, nums.length - 1, target, 0);}public int findTargetSumWaysHelper(int[] nums, int curIdx, int target, int curSum) {Map.Entry<Integer, Integer> curEntry = Map.entry(curIdx, curSum);if (this.state.containsKey(curEntry)) {return this.state.get(curEntry);}if (curIdx < 0 && curSum == target) {return 1;} else if (curIdx < 0) {return 0;}int positive = findTargetSumWaysHelper(nums, curIdx - 1, target, curSum + nums[curIdx]);int negative = findTargetSumWaysHelper(nums, curIdx - 1, target, curSum - nums[curIdx]);this.state.put(curEntry, positive + negative);return positive + negative;}public void initArray(int[] nums) {int absSum = 0;int length = nums.length;for (int i = 0; i < length; i++) {absSum += Math.abs(nums[i]);}this.absSum = absSum;this.dp = new int[length][absSum * 2 + 1];for (int i = 0; i < length; i++) {Arrays.fill(this.dp[i], -1);}}public int findTargetSumWaysHelperOpti(int[] nums, int curIdx, int target, int curSum) {if (curIdx >= 0 && this.dp[curIdx][curSum + this.absSum] != -1) {return this.dp[curIdx][curSum + this.absSum];}if (curIdx < 0 && curSum == target) {return 1;} else if (curIdx < 0) {return 0;}int positive = findTargetSumWaysHelperOpti(nums, curIdx - 1, target, curSum + nums[curIdx]);int negative = findTargetSumWaysHelperOpti(nums, curIdx - 1, target, curSum - nums[curIdx]);int res = positive + negative;this.dp[curIdx][this.absSum + curSum] = res;return res;}
}

10. 正则表达式匹配
题目概述：给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘’ 的正则表达式匹配。‘.’ 匹配任意单个字符，'’ 匹配零个或多个前面的那一个元素。所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

class Solution {public boolean isMatch(String s, String p) {/* 1.第一种方案使用递归实现，因为*的特性，从后往前遍历动态规划的方案理解起来有些困难，不看了哈哈*/int sLength = s.length();int pLength = p.length();if (pLength == 0) {return sLength == 0;} else if (sLength == 0) {char lastChar = getLastChar(p, pLength);if (lastChar != '*') {return false;} else {return isMatch(s, p.substring(0, pLength - 2));}} else {char lastChar = getLastChar(p, pLength);switch (lastChar) {case '.':return isMatch(s.substring(0, sLength - 1), p.substring(0, pLength - 1));case '*':char lastSecondChar = getLastChar(p, pLength - 1);String pSubString = p.substring(0, pLength - 2);if (lastSecondChar == getLastChar(s, sLength) || lastSecondChar == '.') {return isMatch(s, pSubString) || isMatch(s.substring(0, sLength - 1), p);} else {return isMatch(s, pSubString);}default:if (getLastChar(s, sLength) == getLastChar(p, pLength)) {return isMatch(s.substring(0, sLength - 1), p.substring(0, pLength - 1));} else {return false;}}}}public char getLastChar(String s, int length) {return s.charAt(length - 1);}
}

32. 最长有效括号
题目概述：给你一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

class Solution {public int longestValidParentheses(String s) {/* 1.第一种方案，参考的题解使用栈来做，将所有匹配的括号的索引放入数组，再对数组进行排序，找到最长的连续数字即为所求*/if (s.length() == 0) {return 0;}Stack<Character> charStack = new Stack<>();Stack<Integer> idxStack = new Stack<>();int[] nums = new int[s.length()];Arrays.fill(nums, -1);int idx = 0;for (int i = 0; i < s.length(); i++) {char curChar = s.charAt(i);if (charStack.size() == 0) {charStack.add(curChar);idxStack.add(i);} else {if (curChar == ')' && charStack.peek() == '(') {charStack.pop();nums[idx++] = idxStack.pop();nums[idx++] = i;} else {charStack.push(curChar);idxStack.push(i);}}}Arrays.sort(nums);int res = 0;int curStart = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] == -1) {continue;}curStart = i;while (curStart != nums.length - 1 && nums[curStart + 1] - nums[curStart] == 1) {curStart++;}res = res > curStart - i + 1 ? res : curStart - i + 1;}return res;/* 2.第二种方案，同样参考的题解使用动态规划完成dp[i] = 以s[i]为结尾的最长字串的长度s[i] = '(' -> dp[i] = 0;s[i] = ')' -> 有两种情况，比较复杂，一般想不出来dp[0] = 0;dp[1] = 0;*/int length = s.length();if (length < 2) {return 0;}int[] dp = new int[length];dp[0] = 0;int res = 0;for (int i = 1; i < length; i++) {if (s.charAt(i) == '(') {dp[i] = 0;} else {if (s.charAt(i - 1) == '(') {if (i > 2) {dp[i] =  dp[i - 2] + 2;} else {dp[i] = 2;}} else if (s.charAt(i - 1) == ')') {int prev = i - dp[i - 1] - 1;if (prev > 0 && s.charAt(prev) == '(') {dp[i] = dp[i - 1] + 2 + dp[prev - 1];} else if (prev == 0 && s.charAt(prev) == '(') {dp[i] = dp[i - 1] + 2;} else {dp[i] = 0;}}}res = dp[i] > res ? dp[i] : res;}return res;}
}

动态规划类型总结

总结，动态规划类

To be a sailor of the world bound for all ports.

查看全文中文繁体

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.exyb.cn/news/show-4502160.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！