[数据结构与算法]leetcode 1035 不相交的线

前言

题目：1035. 不相交的线

参考题解：不相交的线-代码随想录

提交代码

因为刚敲了leetcode 1143 最长公共子序列，所以能想到本题是对最长公共子序列的应用。要是哪天临时看到这一题，估计会想不出来这个转换关系。

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
        // 最长公共子序列的应用
        int len1 = nums1.size();
        int len2 = nums2.size();
        vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));

        for(int i=1; i<=len1; i++){
            for(int j=1; j<=len2; j++){
                if(nums1[i-1] == nums2[j-1])
                    dp[i][j] = dp[i-1][j-1] + 1;
                else
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }

        return dp[len1][len2];
    }
};