leetcode 1035 不相交的线

2021/10/27 23:15:54

本文主要是介绍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];
    }
};


这篇关于leetcode 1035 不相交的线的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程