算法训练day53|动态规划part14

发布时间:2023年12月31日

?

参考:代码随想录

1143.最长公共子序列

重点:状态的转移与递推公式的确定

本题和动态规划:718. 最长重复子数组?(opens new window)区别在于这里不要求是连续的了,但要有相对顺序,即:"ace" 是 "abcde" 的子序列,但 "aec" 不是 "abcde" 的子序列。

递推公式

主要就是两大情况: text1[i - 1] 与 text2[j - 1]相同,text1[i - 1] 与 text2[j - 1]不相同

如果text1[i - 1] 与 text2[j - 1]相同,那么找到了一个公共元素,所以dp[i][j] = dp[i - 1][j - 1] + 1;

如果text1[i - 1] 与 text2[j - 1]不相同,那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列,取最大的

即:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

遍历顺序

可知循环内从前往后遍历

1035.不相交的线

直线不能相交,这就是说明在字符串A中 找到一个与字符串B相同的子序列,且这个子序列不能改变相对顺序,只要相对顺序不改变,链接相同数字的直线就不会相交

这么分析完之后,大家可以发现:本题说是求绘制的最大连线数,其实就是求两个字符串的最长公共子序列的长度

相当于就是1143题

53. 最大子序和

1. dp数组(dp table)以及下标的含义

dp[i]:包括下标i(以nums[i]为结尾)的最大连续子序列和为dp[i]

2.递推公式

dp[i]只有两个方向可以推出来:

  • dp[i - 1] + nums[i],即:nums[i]加入当前连续子序列和
  • nums[i],即:从头开始计算当前连续子序列和

一定是取最大的,所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

3. 初始化

dp[0]=nums[0];

4. 递推顺序

dp[i]依赖于dp[i - 1]的状态,需要从前向后遍历。

返回是所有dp的最大值(因为是以某个点结尾的最大序列,包含最后一个并不一定是最大值)

还可以用贪心算法,其实跟动态规划的想法有相通之处

文章来源:https://blog.csdn.net/AdrianLeon/article/details/135311073
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。