dp2——子数组/子序列
能帮到你的话，就给个赞吧 😘
文章目录
子数组/子序列
有些人一直区分不清子数组和子序列，其实很简单。
数组vector& nums = {1, 2, 3, 4, 5};
[1, 2, 3]就是子数组
[1, 2, 4]就是子序列。
所以，子数组是子序列的子集。即[1, 2, 3] 既是子数组，也是子序列。
所以，适用子序列的解就能解子数组。
数组
下位
01 53. 最大子数组和⭐——遍历&dp
思想⭐⭐
这题dp的特点是非常明显的，即最优+区域点到点。
但如果同路径一样直接返回点到底这个区域的最优，是无法解的。
因为有一个细小的盲点。都是点到底，
路径求的是区域中的最优路径，最优路径一定是点到底的。
子数组求的是区域中的最优子数组，但最优子数组并不一定是点到底的。
没错，这就是dp定义的另一个关键点。
即最优一定是点到底的。(工程版) (底可以抽象，但点必须)
为什么呢？因为dp需要dp来推导，但如果dp返回的是随机的，不一定是点到底，那该如何推呢。
即无后效性。(理论版)
所以，我们直接定义点到底，即dp(nums, i)是以i开始到底的最大子数组。
此题便变成了遍历&dp。
同时这样定义，不会漏掉任何一个子数组。
这种思想是两星，但由于这就是子数组&子序列的通用定义，故给一星。
02 152. 乘积最大子数组
序列
下位
01 115. 不同的子序列
02 300. 最长递增子序列
03 392. 判断子序列
04 516. 最长回文子序列
05 792. 匹配子序列的单词数
06 1143. 最长公共子序列
07 1425. 带限制的子序列和
原文地址：https://blog.csdn.net/qq_42863961/article/details/136475223
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！