🪴 Quartz 4.0

线性 dp

4 min read

背包也是一种线性 dp，其实就是看可能多维的状态，是不是有一个明显的顺序去计算。比如背包就是一行一行递增或递减着去计算

例：三角形数字路径

下标从几开始

一般涉及 i-1 就会从 1 开始比较好

其实 打家劫舍 那题那个做法就是从 2 开始

例：最长递增子序列

我先自己写一下。我先是想了一个状态计算的方案：dp[i] 是比较 a[i-1] 大小关系后再决定的。但是这样的话，如果上一个根本就不是 a[i-1]，那和它比较是不是有点荒唐？所以我 dp 再开一维 2 空间，用来保存最后到底是谁，也就是保存两个属性

但是还是有问题，这样比如 1 8 2 3 4，到 1 8 就是 2 了，234 加不进来，答案就错了，所以每次都要和过往所有的比较

既然要和所有的比，那就说明我要访问的元素 (其实就是 dp) 要能保存，保存选了 i 的最大值。诶不对啊，但是最后返回值不一定一定选最后一个元素啊

for(int i = 2; i <= n; ++i) {
	for(int j = 0; j < i; ++j) {
		if(a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1);
	}
}
int ans = -1;
for(int i = 1; i <= n; ++i) {
	ans = max(ans, dp[i]);
}
return ans;

最终结果不一定是 dp

这告诉我了要变通，最终答案不一定就是 dp[n]，也可能是一个族

例：最长公共子序列

acbd 和 abedc 最长公共子序列是 abd，也就是 3

这种两个序列的我还是第一次见，我想半天没想出来。首先这里是两维了 (别问为什么)，那明显表示 ij 位置的公共子序列的最大长度

for(int i = 1; i <= n; ++i) {
	for(int j = 1; j <= m; ++j) {
		if(a[i] == a[j]) dp[i][j] = dp[i-1][j-1] + 1;
		else dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
	}
}
return dp[n][m];

我这个果然也挑不出漏洞，网上搜了一下，这个方法也是正确的，只是 y 总教的不是这个方法，不过说说不是这个方法，其实殊途同归：说是 ij 包不包含分为四类

  • 全包含：dp[i-1][j-1] + 1 和我的一样
  • 全不包含：dp[i-1][j-1]
  • 包含他/包含我：实际上这个并不好算，dp[i][j-1] 这个只代表 i，j-1 的最长公共，不一定一定包含谁

不过实际上 dp[i][j-1] 和 dp[i-1][j] 覆盖了全不包含的情况，所以综合下来和我的一样

总结

这里 bb 半天到底想说啥，就是按 y 总的四类分最后化简能够确保一定正确，有的人可能正确答案是半蒙半猜的，那这样很容易做错

然而我想到的这个一步到位的化简我认为是有理可循的，只要有理可循，那就是正确的

Graph View

Backlinks