算法系列--两个数组的dp问题(2)（上）
https://developer.aliyun.com/article/1480832?spm=a2c6h.13148508.setting.14.5f4e4f0eTjofy2
💕"往前走"💕
作者：Mylvzi
文章主要内容：算法系列–两个数组的dp问题(2)
大家好,今天为大家带来的是
算法系列--两个数组的dp问题(2),今天的题目相较于(1)简单很多
2.两个字符串的最⼩ ASCII 删除和
链接:
https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/description/
分析:
本题可以采用正难则反的思想解决,因为这样可以转化为我们已经学习过的最长公共子序列的问题,题目要求删除的字符的ascii码值最小,那么我们可以求出公共子序列中ascii码值最大的,再用字符串的ascii码和减去这个值就能得到答案
- 状态表示:
dp[i][j]:s1[0,i]区间内和s2[0,j]区间内所有的公共子序列中最大的ascii码值 - 状态转移方程:和
最长公共子序列的分析方式相同s1[i] == s2[j]:则最大ascii码值的公共子序列一定以i,j结尾,dp[i][j] = dp[i - 1][j - 1] + s1[i]s1[i] != s2[j],dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1])
代码:
class Solution { public int minimumDeleteSum(String s1, String s2) { int m = s1.length(), n = s2.length(); int[][] dp = new int[m + 1][n + 1];// 创建dp表 for(int i = 1; i <= m; i++) {// 填表 for(int j = 1; j <= n; j++) { if(s1.charAt(i - 1) == s2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + s1.charAt(i - 1); else dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]); } } int sum = 0;// 记录两个字符串所有字符的ascii码和 for(char ch : s1.toCharArray()) sum += ch; for(char ch : s2.toCharArray()) sum += ch; return sum - dp[m][n] - dp[m][n];// 返回值 } }
3.最⻓重复⼦数组
链接:
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
分析:
本题其实是一个子数组问题,子数组问题的状态表示一般是以i位置为结尾xxxx
- 状态表示:
dp[i][j] : nums1以i位置为结尾,nums2以j位置为结尾的所有公共子数组的最大长度 - 状态转移方程:只有当
nums1[i] == nums2[j]成立时,才符合公共子数组(子数组问题要求必须以最后一个位置为结尾,就是必须包含最后一个位置的字符)
代码:
class Solution { public int findLength(int[] nums1, int[] nums2) { int m = nums1.length, n = nums2.length; int[][] dp = new int[m + 1][n + 1];// 创建dp表 int ret = -0x3f3f3f3f;// 记录最大值 for(int i = 1; i <= m; i++) { for(int j = 1; j <= n; j++) { if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1; ret = Math.max(ret,dp[i][j]);// 更新最值 } } return ret; } }
