Day44——Dp专题 柔情只为你懂 2024-03-30 11:53 57阅读 0赞 #### 文章目录 #### * * 子序列问题 * * 27.最长递增子序列 * 28、最长连续递增序列 * 29、最长重复子数组 * 30、最长公共子序列 * 31、不相交的线 * 32、最大子序和 * 33、判断子序列 * 34、不同的子序列 * 35、两个字符串的删除操作 * 36、编辑距离 * 37、回文子串 * 38、最长回文子序列 * 动态规划总结篇 * * 背包问题系列 * 股票系列 * 子序列系列 -------------------- ### 子序列问题 ### #### 27.最长递增子序列 #### [力扣题目链接][Link 1] 状态表示：`dp[i]`：包含`i`的前`i`之前的以`nums[i]`结尾的最长上升子序列长度 状态计算：由于是不连续的，我们考虑最后一个，要计算`dp[i]`就要全部考虑`nums[0 ~ i-1]即 j来枚举nums[0~i-1]`， if(nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1) **动规五部曲** * **确定dp数组以及下标的含义** dp\[i\]表示i之前包括i的以nums\[i\]结尾的最长递增子序列的长度 * **确定递推公式** `if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);` 注意这里不是要`dp[i] 与 dp[j] + 1`进行比较，而是我们要取dp\[j\] + 1的最大值。 for(int i = 0;i < n;i++){ for(int j = 0;j < i;j++){ if(nums[i] > nums[j]){ dp[i] = Math.max(dp[i],dp[j]+1); } } * **dp数组初始化** 每一个i，对应的`dp[i]`（即最长递增子序列）起始大小至少都是1。 Arrays.fill(dp,1); * **确定遍历顺序** 那么遍历i,j一定是从前向后遍历 * **打印并举例推导dp数组** ![image-20221223185110498][] **Code** class Solution { public int lengthOfLIS(int[] nums) { int[] dp = new int[nums.length]; int n = nums.length; Arrays.fill(dp,1); int res = 1; for(int i = 0;i < n;i++){ for(int j = 0;j < i;j++){ if(nums[i] > nums[j]){ dp[i] = Math.max(dp[i],dp[j]+1); } } res = Math.max(res,dp[i]); } return res; } } #### 28、最长连续递增序列 #### [力扣题目链接][Link 2] 状态表示：`dp[i]`：表示包含`i`的以`nums[i]`结尾的最长连续递增序列的长度为`dp[i]` 由于是连续的我们就只要比较相邻前后两个元素与`i-1`比较即可，不用像不连续的`最长递增子序列`那样与`j : 0~i-1`上的数进行比较 **动规五部曲** * **确定dp数组以及下标的含义** dp\[i\]：以下标i为结尾的连续递增的子序列长度为dp\[i\]。 * **确定递推公式** 如果 `nums[i] > nums[i - 1]`，那么以 i 为结尾的连续递增的子序列长度 一定等于以i - 1为结尾的连续递增的子序列长度 + 1 。 即：dp\[i\] = dp\[i - 1\] + 1; for(int i = 1;i < n;i++){ if(nums[i] > nums[i-1]){ dp[i] = Math.max(dp[i],dp[i-1]+1); } res = Math.max(res,dp[i]); } * **dp数组初始化** 从前向后遍历,因为只需要与前一个进行比较，所以dp数组都初始化1 Arrays.fill(dp,1); * **确定遍历顺序** 所以一定是从前向后遍历。 * **举例并推导dp数组** ![image-20221223192831095][] **Code** class Solution { public int findLengthOfLCIS(int[] nums) { int[] dp = new int[nums.length]; int n = nums.length; Arrays.fill(dp,1); int res = 1; for(int i = 1;i < n;i++){ if(nums[i] > nums[i-1]){ dp[i] = Math.max(dp[i],dp[i-1]+1); } res = Math.max(res,dp[i]); } return res; } } #### 29、最长重复子数组 #### [力扣题目链接][Link 3] 状态表示：`f[i][j]`：nums1\[0~i-1\]以`nums1[i - 1]`结尾的和nums2\[0~j-1\]以`nums2[j - 1]`结尾的最长重复子数组长度为`f[i][j]` 属性：`Max_count` 初始化： 根据`dp[i][j]`的定义，`dp[i][0] 和dp[0][j]`其实都是没有意义的！（-1怎么结尾呢是吧） 但`dp[i][0]`和`dp[0][j]`要初始值，因为 为了方便递归公式`dp[i][j] = dp[i - 1][j - 1] + 1;` 所以`dp[i][0] 和dp[0][j]`初始化为`0`。 **动态规划五部曲：** * **确定dp数组以及下标的含义** `dp[i][j]` ：以下标i - 1为结尾的A，和以下标j - 1为结尾的B，最长重复子数组长度为`dp[i][j]`。 （**特别注意**： “以下标i - 1为结尾的A” 标明一定是 以A\[i-1\]为结尾的字符串 ） * **确定递推公式** 根据`dp[i][j]`的定义，`dp[i][j]`的状态只能由`dp[i - 1][j - 1]`推导出来。 即当A\[i - 1\] 和B\[j - 1\]相等的时候，`dp[i][j] = dp[i - 1][j - 1] + 1;` for(int i = 1;i < n;i++){ for(int j = 1;j < m;j++){ if(nums1[i-1] == nums2[j-1]){ dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1); } res = Math.max(dp[i][j],res); } } * **dp数组如何初始化** `dp[i][0] 和dp[0`\]\[j\]要初始值，因为 为了方便递归公式`dp[i][j] = dp[i - 1][j - 1] + 1`; 所以`dp[i][0] 和dp[0][j]`初始化为0。 * **确定遍历顺序** 所以一定是从前向后遍历。 * **举例推导dp数组** ![image-20221223201859533][] **Code** class Solution { public int findLength(int[] nums1, int[] nums2) { int[][] dp = new int[nums1.length+1][nums2.length+1]; int n = nums1.length + 1; int m = nums2.length + 1; int res = 0; for(int i = 1;i < n;i++){ for(int j = 1;j < m;j++){ if(nums1[i-1] == nums2[j-1]){ dp[i][j] = Math.max(dp[i][j],dp[i-1][j-1]+1); } res = Math.max(dp[i][j],res); } } return res; } } #### 30、最长公共子序列 #### [力扣题目链接][Link 4] **四种基本状态** `dp[i-1][j-1]` `dp[i][j-1]` `dp[i-1][j]` `dp[i][j]` 1.**确定dp数组（dp table）以及下标的含义** `dp[i][j]`：长度为\[0, i - 1\]的字符串text1与长度为\[0, j - 1\]的字符串text2的最长公共子序列为`dp[i][j]` 2.**确定递推公式** text1\[i - 1\] 与 text2\[j - 1\]相同，text1\[i - 1\] 与 text2\[j - 1\]不相同 如果text1\[i - 1\] 与 text2\[j - 1\]相同，那么找到了一个公共元素，所以`dp[i][j] = dp[i - 1][j - 1] + 1`; 如果text1\[i - 1\] 与 text2\[j - 1\]不相同，那就看看text1\[0, i - 2\]与text2\[0, j - 1\]的最长公共子序列 和 text1\[0, i - 1\]与text2\[0, j - 2\]的最长公共子序列，取最大的。 即：`dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])`; if(char1 == char2){ dp[i][j] = dp[i-1][j-1] + 1; } else{ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); } 3.**dp数组如何初始化** `dp[i][0] = 0;` `dp[0][j]也是0。` 4.**确定遍历顺序** ![image-20221223210201175][] 5.**举例推导dp数组** ![image-20221223210201175][] **Code** class Solution { public int longestCommonSubsequence(String text1, String text2) { int[][] dp = new int[text1.length()+1][text2.length()+1]; int n = text1.length()+1; int m = text2.length()+1; int res = 0; for(int i = 1;i < n;i++){ for(int j = 1;j < m;j++){ char char1 = text1.charAt(i-1); char char2 = text2.charAt(j-1); if(char1 == char2){ dp[i][j] = dp[i-1][j-1] + 1; } else{ dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]); } res = Math.max(res,dp[i][j]); } } return res; } } #### 31、不相交的线 #### [力扣题目链接][Link 5] 要求相等且不相交且要最长的———— 其实就是最长公共子序列！ **Code** class Solution { public int maxUncrossedLines(int[] nums1, int[] nums2) { int n = nums1.length; int m = nums2.length; int res = 0; int[][] dp = new int[n+1][m+1]; for(int i = 1;i < n + 1;i++){ for(int j = 1;j < m + 1;j++){ if(nums1[i - 1] == nums2[j - 1]){ dp[i][j] = dp[i-1][j-1] + 1; } else{ dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j]); } res = Math.max(res,dp[i][j]); } } return dp[n][m]; } } #### 32、最大子序和 #### [力扣题目链接][Link 6] 状态表示`dp[i]`：表示以`nums[i]`结尾的最大连续子段和，`dp[i]`只与`dp[i - 1]`有关 属性：`Max` 假设数组 `nums` 的值全都严格大于 0，那么一定有 `dp[i] = dp[i - 1] + nums[i]`。 状态转移：但由于存在负数的情况，因此要分类讨论： * `dp[i - 1] <= 0`，那么`dp[i]`要是加上它反而变小了，为此`dp[i] = nums[i]` * `dp[i - 1] > 0`，那么 `dp[i] = dp[i - 1] + nums[i]` * 初始化：`f[0] = nums[0]`，以`nums[0]`结尾的和即为它本身。 **动规五部曲** * **确定dp数组以及其下标的含义** dp\[i\]表示以`nums[i]`结尾的最大连续子段和 * **确定递推公式** dp\[i\]只有两个方向可以推出来： * dp\[i - 1\] + nums\[i\]，即：nums\[i\]加入当前连续子序列和 * nums\[i\]，即：从头开始计算当前连续子序列和 * **dp数组初始化** dp\[0\]应为nums\[0\]即dp\[0\] = nums\[0\]。 * **确定遍历顺序** 递推公式中dp\[i\]依赖于dp\[i - 1\]的状态，需要从前向后遍历。 * **举例并推导dp数组** ![image-20221224125510584][] 那么我们要找最大的连续子序列，就应该找每一个i为终点的连续最大子序列。 所以在递推公式的时候，可以直接选出最大的dp\[i\]。 **Code** class Solution { public int maxSubArray(int[] nums) { int n = nums.length; int[] dp = new int[n]; dp[0] = nums[0]; int res = nums[0]; for(int i = 1;i < n;i++){ dp[i] = Math.max(dp[i-1]+nums[i],nums[i]); res = Math.max(res,dp[i]); } return res; } } #### 33、判断子序列 #### [力扣题目链接][Link 7] 状态计算： * `if (s[i] == t[j ])`，那么`dp[i][j] = dp[i - 1][j - 1] + 1;`，因为找到了一个相同的字符，相同子序列长度自然要在`dp[i-1][j-1]的`基础上加`1` * `if (s[i ] != t[j])`，此时相当于t要删除元素，t如果把当前元素`t[j ]`删除，使得`s[1~i]与t[1 ~ j-1]`相匹配！即`dp[i][j] = dp[i][j - 1];` if(char1 == char2){ dp[i][j] = dp[i-1][j-1] + 1; }else{ dp[i][j] = dp[i][j-1]; } **动规五部曲** * **确定dp数组以及下标的含义** `dp[i][j]` 表示以下标i-1为结尾的字符串s，和以下标j-1为结尾的字符串t，相同子序列的长度为`dp[i][j]`。 * **确定递推公式** `if (s[i - 1] == t[j - 1])，dp[i][j] = dp[i - 1][j - 1] + 1;` `if (s[i - 1] != t[j - 1])，dp[i][j] = dp[i][j - 1];` * **dp数组初始化** \`\`dp\[i\]\[j\]`都是依赖于`dp\[i - 1\]\[j - 1\] 和 dp\[i\]\[j - 1\]`，所以`dp\[0\]\[0\]和dp\[i\]\[0\]\`都要初始化 * **确定遍历顺序** ![image-20221224132848544][] * **举例并推导dp数组** ![image-20221224132848544][] `dp[i][j]`表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t 相同子序列的长度，所以如果`dp[s.size()][t.size()]` 与 字符串s的长度相同说明：s与t的最长相同子序列就是s，那么s 就是 t 的子序列。 if(res == n){ return true; }else{ return false; } **Code** class Solution { public boolean isSubsequence(String s, String t) { int n = s.length(); int m = t.length(); int[][] dp = new int[n+1][m+1]; int res = 0; for(int i = 1;i < n + 1;i++){ for(int j = 1;j < m + 1;j++){ char char1 = s.charAt(i-1); char char2 = t.charAt(j-1); if(char1 == char2){ dp[i][j] = dp[i-1][j-1] + 1; }else{ dp[i][j] = dp[i][j-1]; } res = Math.max(res,dp[i][j]); } } if(res == n){ return true; }else{ return false; } } } #### 34、不同的子序列 #### [力扣题目链接][Link 8] ![image-20221224145309217][] **动规五部曲** * **确定dp数组以及其下标的含义** `dp[i][j]`：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为`dp[i][j]`。 * **确定递推公式** * s\[i - 1\] 与 t\[j - 1\]相等 * 用s\[i - 1\]来匹配，个数为`dp[i - 1][j - 1]`。 * 不用s\[i - 1\]来匹配，个数为`dp[i - 1][j]`。 * s\[i - 1\] 与 t\[j - 1\] 不相等 * 个数为`dp[i - 1][j]`。 if(s.charAt(i - 1) == t.charAt(j - 1)){ dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; }else{ dp[i][j] = dp[i - 1][j]; } * **dp数组初始化** `dp[i][0]`应初始化为1，其余初始化为0 * **确定遍历顺序** 从递推公式`dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; 和 dp[i][j] = dp[i - 1][j];` 中可以看出`dp[i][j]`都是根据左上方和正上方推出来的。 所以遍历的时候一定是从上到下，从左到右 * **举例并推导dp数组** ![image-20221224145733382][] **Code** class Solution { public int numDistinct(String s, String t) { int n = s.length(); int m = t.length(); int[][] dp = new int[n+1][m+1]; for(int i = 0;i < n + 1;i++){ dp[i][0] = 1; } for(int i = 1;i < n + 1;i++){ for(int j = 1;j < m + 1;j++){ if(s.charAt(i - 1) == t.charAt(j - 1)){ dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; }else{ dp[i][j] = dp[i - 1][j]; } } } return dp[n][m]; } } #### 35、两个字符串的删除操作 #### [力扣题目链接][Link 9] ![image-20221224160141504][] 思路一： 求出两个字符串的**最长公共子序列长度**即可，那么除了最长公共子序列之外的字符都是必须删除的，最后用两个字符串的**总长度减去两个最长公共子序列的长度**就是删除的最少步数。 思路二： **动规五部曲** * **确定dp数组以及下标的含义** `dp[i][j]`：以i-1为结尾的字符串word1，和以j-1位结尾的字符串word2，想要达到相等，所需要删除元素的最少次数。 * **确定递推公式** * 当word1\[i - 1\] 与 word2\[j - 1\]相同的时候 * 当word1\[i - 1\] 与 word2\[j - 1\]不相同的时候 当word1\[i - 1\] 与 word2\[j - 1\]相同的时候，`dp[i][j] = dp[i - 1][j - 1];` 当word1\[i - 1\] 与 word2\[j - 1\]不相同的时候，有三种情况： 情况一：删word1\[i - 1\]，最少操作次数为`dp[i - 1][j] + 1` 情况二：删word2\[j - 1\]，最少操作次数为`dp[i][j - 1] + 1` 情况三：同时删word1\[i - 1\]和word2\[j - 1\]，操作的最少次数为`dp[i - 1][j - 1] + 2` 那最后当然是取最小值，所以当word1\[i - 1\] 与 word2\[j - 1\]不相同的时候，递推公式：`dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1});` * **dp数组初始化** `dp[i][0] 和 dp[0][j]`是一定要初始化的 for(int i = 0;i < n + 1;i++) dp[i][0] = i; for(int j = 0;j < m + 1;j++) dp[0][j] = j; * **确定遍历顺序** 从递推公式 `dp[i][j] = min(dp[i - 1][j - 1] + 2, min(dp[i - 1][j], dp[i][j - 1]) + 1); 和dp[i][j] = dp[i - 1][j - 1]`可以看出`dp[i][j]`都是根据左上方、正上方、正左方推出来的。 * **举例并推导dp数组** ![image-20221224155321226][] **Code** 解法一 // dp数组中存储word1和word2最长相同子序列的长度 class Solution { public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); int[][] dp = new int[n+1][m+1]; for(int i = 1;i < n + 1;i++){ for(int j = 1;j < m + 1;j++){ if(word1.charAt(i - 1) == word2.charAt(j - 1)){ dp[i][j] = dp[i - 1][j - 1] + 1; }else{ dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]); } } } return n + m - 2*dp[n][m]; } } 解法二 class Solution { public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); int[][] dp = new int[n+1][m+1]; for(int i = 0;i < n + 1;i++) dp[i][0] = i; for(int j = 0;j < m + 1;j++) dp[0][j] = j; for(int i = 1; i < n + 1;i++){ for(int j = 1;j < m + 1;j++){ if(word1.charAt(i - 1) == word2.charAt(j - 1)){ dp[i][j] = dp[i-1][j-1]; }else{ dp[i][j] = Math.min(Math.min(dp[i-1][j] + 1,dp[i][j-1]+1),dp[i-1][j-1]+2); } } } return dp[n][m]; } } #### 36、编辑距离 #### [力扣题目链接][Link 10] **动规五部曲** * **确定dp数组以及下标的含义** `dp[i][j] 表示以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]。` * **确定递推公式** if (word1[i - 1] == word2[j - 1]) 不操作 if (word1[i - 1] != word2[j - 1]) 增 删 换 * `word1[i - 1] == word2[j - 1]` * 不操作 `dp[i][j] = dp[i-1][j-1]` * `word1[i - 1] != word2[j - 1]` * 增和删等同，操作数一样 * `dp[i][j] = dp[i][j-1] + 1` * `dp[i][j] = dp[i-1][j] + 1` * 换 * `dp[i][j] = dp[i-1][j-1] + 1` * 在增删换最小值 dp[i][j] = Math.min(Math.min(dp[i - 1][j],dp[i][j - 1]),dp[i - 1][j - 1])+1; * **dp数组初始化** `p[i][0] = i;` `dp[0][j] = j`; for(int i = 0;i < n + 1;i++) dp[i][0] = i; for(int j = 0;j < m + 1;j++) dp[0][j] = j; * **确定遍历顺序** 从如下四个递推公式： * `dp[i][j] = dp[i - 1][j - 1]` * `dp[i][j] = dp[i - 1][j - 1] + 1` * `dp[i][j] = dp[i][j - 1] + 1` * `dp[i][j] = dp[i - 1][j] + 1` **dp矩阵中一定是从左到右从上到下去遍历** ![image-20221224162301543][] * **打印并推导dp数组** 以示例1为例，输入：`word1 = "horse", word2 = "ros"`为例，dp矩阵状态图如下： ![image-20221224162400183][] **Code** class Solution { public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); int[][] dp = new int[n+1][m+1]; for(int i = 0;i < n + 1;i++) dp[i][0] = i; for(int j = 0;j < m + 1;j++) dp[0][j] = j; for(int i = 1; i < n + 1;i++){ for(int j = 1;j < m + 1;j++){ if(word1.charAt(i - 1) == word2.charAt(j - 1)){ dp[i][j] = dp[i - 1][j - 1]; }else{ dp[i][j] = Math.min(Math.min(dp[i - 1][j],dp[i][j - 1]),dp[i - 1][j - 1])+1; } } } return dp[n][m]; } } #### 37、回文子串 #### [力扣题目链接][Link 11] **动规五部曲** * **确定dp数组以及其下标的含义** 布尔类型的dp\[i\]\[j\]：表示区间范围\[i,j\] （注意是左闭右闭）的子串是否是回文子串，如果是dp\[i\]\[j\]为true，否则为false。 * **确定递推公式** 整体上是两种，就是s\[i\]与s\[j\]相等，s\[i\]与s\[j\]不相等这两种。 当s\[i\]与s\[j\]不相等，那没啥好说的了，`dp[i][j]`一定是false。 当s\[i\]与s\[j\]相等时，这就复杂一些了，有如下三种情况 * 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串 * 情况二：下标i 与 j相差为1，例如aa，也是回文子串 * 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s\[i\]与s\[j\]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看`dp[i + 1][j - 1]`是否为true。 if(s.charAt(i) == s.charAt(j)){ if(j - i <= 1){ dp[i][j] = true; res++; }else if(dp[i+1][j-1]){ dp[i][j] = true; res++; * **dp数组初始化** `dp[i][j]`初始化为false。 * **确定遍历顺序** `dp[i + 1][j - 1] 在 dp[i][j]`的左下角，如图： ![image-20221224172736036][] 一定要从下到上，从左到右遍历，这样保证`dp[i + 1][j - 1]`都是经过计算的 * **举例并推导dp数组** 举例，输入：“aaa”，`dp[i][j]`状态如下： ![image-20221224172832268][] **Code** class Solution { public int countSubstrings(String s) { int res = 0; if(s == null || s.length() == 0) return 0; int n = s.length(); boolean[][] dp = new boolean[n][n]; for(int i = n - 1;i >= 0;i--){ for(int j = i;j < n;j++){ if(s.charAt(i) == s.charAt(j)){ if(j - i <= 1){ dp[i][j] = true; res++; }else if(dp[i+1][j-1]){ dp[i][j] = true; res++; } } } } return res; } } #### 38、最长回文子序列 #### [力扣题目链接][Link 12] **动规五部曲** 状态计算：判断`s[i] 与 s[j]是否相等` * `s[i] == s[j]`： * `dp[i][j] = dp[i + 1][j - 1] + 2` * `s[i] != s[j]：dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])` * 删除`s[i]`：`dp[i + 1][j]` * 删除`s[j]`：`dp[i][j - 1]` * **确定dp数组以及其下标的含义** `dp[i][j]`：字符串s在\[i, j\]范围内最长的回文子序列的长度为`dp[i][j]`。 * **确定递推公式** 如果s\[i\]与s\[j\]相同，那么`dp[i][j] = dp[i + 1][j - 1] + 2;` 如图： ![image-20221224175802025][] `s[i] != s[j]：dp[i][j] = max(dp[i][j - 1], dp[i + 1][j])` 如图： ![image-20221224175848112][] * **dp数组初始化** 当i与j相同，那么`dp[i][j]`一定是等于1，其它情况初始化为0 * **确定遍历顺序** 遍历i的时候一定要从下到上遍历，这样才能保证，下一行的数据是经过计算的。 如图： ![image-20221224180003137][] * **举例并推导dp数组** 输入s:“caad” 为例，dp数组状态如图： ![image-20221224180029924][] **Code** class Solution { public int longestPalindromeSubseq(String s) { int n = s.length(); int[][] dp = new int[n][n]; for(int i = n - 1; i >= 0; i--){ dp[i][i] = 1; for(int j = i + 1; j < n; j++){ if(s.charAt(i) == s.charAt(j)){ dp[i][j] = dp[i+1][j-1] + 2; }else{ dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]); } } } return dp[0][n-1]; } } ### 动态规划总结篇 ### **动规五部曲** * 确定dp数组（dp table）以及下标的含义 * 确定递推公式 * dp数组如何初始化 * 确定遍历顺序 * 举例推导dp数组 #### 背包问题系列 #### ![image-20221224180222405][] #### 股票系列 #### ![image-20221224180333899][] #### 子序列系列 #### ![image-20221224180407568][] [Link 1]: https://leetcode.cn/problems/longest-increasing-subsequence/ [image-20221223185110498]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8fe5e4cbb277437e883c1c36dd294125.png [Link 2]: https://leetcode.cn/problems/longest-continuous-increasing-subsequence/ [image-20221223192831095]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b4bc91faf8b14da5bd369272b1a83cc8.png [Link 3]: https://leetcode.cn/problems/maximum-length-of-repeated-subarray/ [image-20221223201859533]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8bcef84cc6f4466ea9d47da2f8e1d091.png [Link 4]: https://leetcode.cn/problems/longest-common-subsequence/ [image-20221223210201175]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/23a68b7d445247ad80557a30eb4102e6.png [Link 5]: https://leetcode.cn/problems/uncrossed-lines/ [Link 6]: https://leetcode.cn/problems/maximum-subarray/ [image-20221224125510584]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6f56f14c1eeb4dfd9fbbaba9b329f6d8.png [Link 7]: https://leetcode.cn/problems/is-subsequence/ [image-20221224132848544]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/43c1cab4bda444e6aa7c2fe96dbe00d3.png [Link 8]: https://leetcode.cn/problems/distinct-subsequences/ [image-20221224145309217]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8988c455c8ff40eebb245ed5a5acb7cb.png [image-20221224145733382]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/33623704825648c7b59a5e114734a4ed.png [Link 9]: https://leetcode.cn/problems/delete-operation-for-two-strings/ [image-20221224160141504]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e786f47184c44f3ba18a580b63cfbf53.png [image-20221224155321226]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a3f6546b122f465a931f129975e225f7.png [Link 10]: https://leetcode.cn/problems/edit-distance/ [image-20221224162301543]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/73dd3902ba214fd594eecd768f88be2e.png [image-20221224162400183]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a5631eaeb36441f6ad5d181922027af2.png [Link 11]: https://leetcode.cn/problems/palindromic-substrings/ [image-20221224172736036]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/26da604318f9471c880b9c15fd12dc0c.png [image-20221224172832268]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/ba862ff03c5e42c4b919bf9663726055.png [Link 12]: https://leetcode.cn/problems/longest-palindromic-subsequence/ [image-20221224175802025]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e7bf1f75c0594c8a8cb0dfc3f05704e2.png [image-20221224175848112]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/cb120af2786044488cbd92df7af3c41e.png [image-20221224180003137]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/fb46db6ad3f34131ae82673a8f9b10cb.png [image-20221224180029924]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9a9200d1158b475582bea5d7eb742daa.png [image-20221224180222405]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/539d339f551543d6a48e93da2ba0cd9d.png [image-20221224180333899]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0f93fc4fd06c4430ac26147388da8391.png [image-20221224180407568]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/6515196959a343b6afe74e0062df2da3.png
相关 Day38——Dp专题 DP专题 动态规划五部曲： 确定dp数组以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组 1.斐波 怼烎@/ 2024年03月31日 12:42/ 0 赞/ 53 阅读
相关 day44-47 day44内容回顾 HTTP协议 四大特性 1.基于TCP/IP作用于应用层之上的协议 2.基于请 不念不忘少年蓝@/ 2023年10月10日 08:59/ 0 赞/ 51 阅读
相关 dp专题题目记录 1.数的划分 2星 [https://ac.nowcoder.com/acm/problem/16695][https_ac.nowcoder.com_acm_prob 青旅半醒/ 2023年08月17日 16:26/ 0 赞/ 139 阅读
相关 动态规划dp专题 dp专题 斐波那契数列 01背包问题 最长不重复子字符串的长度 分割数组的最大值 最长公共子序列 最大子序和 买卖股票的最佳时期 爱被打了一巴掌/ 2023年07月17日 09:57/ 0 赞/ 5 阅读
朴灿烈づ我的快乐病毒、
怼烎@
柔情只为你懂
红太狼
不念不忘少年蓝@
爱被打了一巴掌
傷城~
还没有评论，来说两句吧...