力扣刷题记录（23）LeetCode：718、1143、1035

718.?最长重复子数组

要想到用一个二维数组dp去表示数组nums1和nums2的公共子数组的最大长度。其中二维数组的索引 i、j 分别表示nums1中[0,i-1]数组、nums2中[0,j-1]数组。如果满足nums1[i-1]==nums2[j-1],那么dp[i][j]=dp[i-1][j-1]+1

class Solution {
public:
    int findLength(vector<int>& nums1, vector<int>& nums2) {
        //dp表示nums1的子串和nums2的子串 的公共最长子数组的长度
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
        int ans=0;
        for(int i=1;i<=nums1.size();i++)
        {
            for(int j=1;j<=nums2.size();j++)
            {
                if(nums1[i-1]==nums2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                //提取最大长度
                ans=max(ans,dp[i][j]);
            }
        }
        return ans;
    }
};

?1143.?最长公共子序列

?

?这题思路和上一题类似，还是用二维数组dp表示公共子序列长度。但难点就在于循坏内该怎么写，也就是递推公式。递推公式分两种情况：

1.text1[i-1]==text2[j-1]

? ? ? ? 这种情况dp[i][j]必然要加1，但问题是应该由哪个dp加1.应该由dp[i-1][j-1]加1，dp[i-1][j-1]才是dp[i][j]的前一个状态。dp[i][j]=dp[i-1][j-1]+1

2.text1[i-1]!=text2[j-1]

? ? ? ? 最长公共子序列会在两种情况间产生，一种是不包含text1[i-1]、一种是不包含text2[j-1].dp[i][j]=max(dp[i-1][j],dp[i][j-1])

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
        int ans=0;
        for(int i=1;i<=text1.size();i++)
        {
            for(int j=1;j<=text2.size();j++)
            {
                //如果相等那最大长度肯定是要加1
                if(text1[i-1]==text2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                //如果不相等 i、j就分别退1取最大值
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                ans=max(ans,dp[i][j]);
            }
        }
        return ans;
    }
};

1035.?不相交的线

这个问题可以直接转换为求最长公共子序列问题，代码同上一题一样。太难想到了

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        vector<vector<int>> dp(nums1.size()+1,vector<int>(nums2.size()+1,0));
        int ans=0;
        for(int i=1;i<=nums1.size();i++)
        {
            for(int j=1;j<=nums2.size();j++)
            {
                //如果相等那最大长度肯定是要加1
                if(nums1[i-1]==nums2[j-1])
                    dp[i][j]=dp[i-1][j-1]+1;
                else
                //如果不相等 i、j就分别退1取最大值
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
                ans=max(ans,dp[i][j]);
            }
        }
        return ans;
    }
};

总结：

动态规划的本质就是当前结果依赖于之前的结果?

?