代码随想录算法训练营第五十三天 |1143. 最长公共子序列、1035. 不相交的线、53. 最大子数组和

1143. 最长公共子序列

题目链接：1143. 最长公共子序列

  • dp含义： nums1[0, i -1]为结尾, nums2 [0, j-1]为结尾的的最长公共子序列的长度

  • 递推公式：

    • if(nums1[i-1] == nums2[j])dp[i][j] = dp[i - 1][j - 1] + 1

    • dp[i] = Math.max(dp[i][j - 1], dp[i-1][j])

  • 初始化：

    • dp[0][j]和dp[i][0]在这样的dp定义下是和空字符串去做比较所以初始化为0，这是巧妙之处所在

1035. 不相交的线

题目链接：1035. 不相交的线

  • 数组保证顺序，约等于上一题

53. 最大子数组和

题目链接：53. 最大子数组和

  • 递推公式： dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容