算法系列--两个数组的dp问题(1)（上）

💕"低头要有勇气，抬头要有底气。"💕

作者：Mylvzi

文章主要内容：算法系列–两个数组的dp问题(1)

大家好,今天为大家带来的是算法系列--两个数组的dp问题(1),两个数组的dp问题在动态规划问题中属于较难的部分,状态转移方程不易推导,希望大家通过下面的几道题目能够掌握

1.最长公共子序列

链接:

https://leetcode.cn/problems/longest-common-subsequence/description/

分析:

题目要找的是两个字符串中,公共子序列的最长长度,也就是要找最长的公共子序列

既然是两个字符串,我们很容易想到dp表应该是一个二维的dp表

dp[i][j]中i是str1的下标,j是str2的下标

根据经验,我们会设出这样的状态表示

dp[i][j]表示str1以i位置为结尾的区间和str2以j位置为结尾的区间内,公共子序列的最长长度

如果以这个状态表示去分析状态转移方程,就会发现错误:

• 如果s[i] == s[j] ,则可以构成公共子序列,此时只需在i-1和j-1区间内求得最长的公共子序列的长度然后再加上1即可,所以 dp[i][j] = dp[i - 1][j - 1] + 1
• 如果 s[i] != s[j] ,此时就无法构成公共子序列,但是状态表示明确指出str1必须以i为结尾,str2必须以j为结尾,也就是公共子序列必须以这两个字符为结尾,逻辑矛盾,无法求出状态转移方程

所以我们要想办法更新一个状态转移方程,分析上述过程,最大的矛盾点在于两个公共子序列不能严格的按照以xxxx为结尾的形式表示,而是应该不限制子序列的开始结束位置,所以可以将状态表示设置为如下:

dp[i][j]:表示str1[0,i]区间内的字符串和str2[0,j]区间内的字符串中,最长的公共子序列的长度

状态转移方程推导:

• 如果s[i] == s[j],则这两个区间内最长的公共子序列一定以(i,j)为结尾;可以利用反证法证明

1. 如果不是以(i,j)为结尾,那么最长的公共子序列可以在内部,但是又由于s[i]==s[j],他们俩也算是公共子序列的一部分,所以还是以s[i]为结尾
2. 还有可能是以(i,j)中一个下标为结尾,另一个不是最长公共子序列的结尾,但是由于,此时还是一定以(i,j)为结尾的
   

• 如果s[i] != s[j],也就是结束的两个字符不同,则最长的公共子序列一定不以这两个位置为结尾,而是以i或者j之前的区间内的某一个位置为结尾,可以分三种情况:

1. [i-1][j]
2. [i][j - 1]
3. [i - 1][j - 1]

dp[i][j]应取这三种情况的最大值

初始化

初始化的目的就是为了防止越界,本题可能出现越界的情况是当i,j为0时

对于二维dp的问题,最常用的一种初始化的方式就是增加一行,增加一列-->dp[m + 1][n + 1]

增加之后就要考虑如何为这些位置赋值了,我们赋值的原则应该是:赋的值应该对之后的填表无影响,或者根据dp表所表示的实际的意义去赋值,本题就利用到这样的想法

试想,第一行表示i==0的情况,此时str1为空字符串(注意下标之间的映射关系),那么根据dp表的含义,此时两个字符串之间不存在公共的子序列,进而也不存在最长的公共子序列长度这一说,所以第一行的所有值应该赋值为0,同样的第一列也要赋值为0

还需要注意的一点是:如果我们扩增了dp表,则dp表与源字符串之间的映射关系发生改变,dp[i + 1] = str[i],dp表的i位置对应的是字符串的的i-1位置,其实这里也可以做一个小优化(字符串的dp问题经常会使用这样的优化),就是让原先的字符串扩增1,str1 = " " + str1,str2 = " " + str2,让两个字符串都拼接一个空格字符,这样他们的长度就+1了,此时dp表的i下标对应的就是字符串的i下标

填表顺序

易得:从上往下,从左至右

返回值

return dp[m][n]

• m == str1.length();
• n == str2.length();

代码实现:

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 1.创建dp表
        int m = text1.length();
        int n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        // 2.初始化
        text1 = " " + text1;
        text2 = " " + text2;
        char[] s1 = text1.toCharArray();
        char[] s2 = text2.toCharArray();
        // 3.填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(s1[i] == s2[j]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
            }
        }
        // 4.返回值
        return dp[m][n];
    }
}

2.不相交的线

链接:

https://leetcode.cn/problems/uncrossed-lines/

分析:

本题的思路和"最长的公共子序列"那道题目的解法相同

代码:

class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        // 本题的思路和"最长的公共子序列"那道题目的解法相同
        int m = nums1.length;
        int n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        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;
                else dp[i][j] = Math.max(dp[i - 1][j],dp[i][j - 1]);
            }
        }
        return dp[m][n];
    }
}

算法系列--两个数组的dp问题(1)（下）https://developer.aliyun.com/article/1480822?spm=a2c6h.13148508.setting.21.361f4f0eyTL4lb