关于动态规划【力扣1143.最长公共子序列的思考】

1、与前几题的区别【力扣300.最长递增子序列】一个数组不连续【力扣674.最长连续递增子序列】一个数组连续【力扣718.最长重复子数组】两个数组连续【力扣1143.最长公共子序列】两个数组不连续本题是求两个数组不连续的最长公共子序列的长度整体代码如下图所示2、递推公式本题与上一题的关键区别在于要求两个数组不连续的最长公共子序列的长度。当前位置dp[i][j]的状态来自三个方向。因为要求不连续的所以只要有一样的就可以把状态转移给下一个【本题】递推公式部分的代码如下图所示【上一题】要求的是连续的当前位置dp[i][j]的状态来自一个方向左上角。因为要求连续的所以必须前一个是连续的才可以把状态转移给下一个。如果前一个不一样当前的一样就要重新开始计算递推公式部分的代码如下图所示3、返回值dp数组里的每个值要么从左上角加1得到要么是上方或左方元素的最大值所以最大值一定出现在右下角所以返回dp[text1.size()][text2.size()]就好。dp[text1.size()][text2.size()]表示以text1.size()-1和text2.size()-1为结尾的最长公共子序列的长度