1.题目解析 

题目来源：1035.不相交的线

测试用例

2.算法原理

本题实质上就是寻找两个数组的最长公共子序列，所以可以直接移步到 最长公共子序列  的解析博客，那里更加详细的介绍了如何处理最长公共子序列的判断

1.状态表示

由题目可知是两个dp表的动态规划问题，那么一维dp表显然无法满足状态表示，所以需要一个二维dp表，这里的dp[i][j]表示：s1字符数组[0,i]区间与s2字符数组[0,j]区间的最长公共子序列的长度

2.状态转移方程 

状态转移方程需要判断最后一个位置的字符是否相等来分类讨论，如下

 

3.初始化 

初始化需要用到空串并且需要注意对于下标映射的处理，如图

4.填表顺序

在填写dp[i][j]时可能用到dp[i-1][j]与dp[i][j-1]以及dp[i-1][j-1]位置的值，那么就需要从上到下，每一行从左到右来填表

5.返回值 

根据状态表示直接返回dp[m][n]即可

3.实战代码

class Solution {
public:int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {int n = nums1.size();int m = nums2.size();vector<vector<int>> dp(n+1,vector<int>(m+1));for(int i = 1;i <= n;i++){for(int j = 1;j <= m;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[n][m];}
};