关于子序列问题的一些思考

首先是状态的定义。
目前做了大概 50 道线性 DP，我发现状态的定义无非是以下两种：
① 前 k 个元素...
② 以第 k 个元素结尾...
省略号代表题目需要维护的状态，比如最值，方案数等等。

其中最常见的应该是 ①，而 ② 似乎只在 Kadane 算法里面使用。
经过思考，我认为：对于子序列问题，① 和 ② 都可以使用；对于子数组问题（可以看成约束更强的子序列问题），只能使用 ②。
如果使用 ② ，在计算最终答案时就需要考虑每一个状态的贡献，而 ① 却不需要，这是因为它是 “增量式” 更新的。
从集合的角度来讲，对于 ① 来说，旧的状态一定是新的状态的子集，所以只需要考虑最后那一个状态；对于 ②，每个状态都是不相交的，因此必须考虑所有状态。

然后，是 “非空” 约束对状态定义的影响。
有些题目认为空的子序列是合法的，而有些题目就不允许这种情况的出现。
这一约束显然会影响边界条件，但我之前一直没有好好思考过它对状态转移方程的影响。
考虑这样一道题：给你一个整数数组（可能有负数），求出最大的子序列和。
这道题可以用贪心解决——只选非负数即可，但这里用 DP 解决。
————
定义状态为前 k 个元素所能得到的最大子序列和。
思考边界条件。
如果允许子序列是空的，那么边界条件是 0；否则，边界条件应该是 ∞（只是一个记号，用来表示非法状态，具体取值视题目要求而定）。
思考状态转移方程。
如果允许子序列是空的，那么有 dp[k] = max(dp[k - 1], dp[k - 1] + v[k])；否则，应该写成 dp[k] = max(dp[k - 1], dp[k - 1] + v[k], v[k])，多了单独的 v[k]。
为什么？因为当前状态可能从非法状态（空的子序列）转移过来，此时那个非法状态相当于 “0”，0 + v[k] 就是 v[k]。

我知道了！等我组织一下语言

错误之处在于 4L 的最后一句话 “当前状态可能从非法状态（空的子序列）转移过来，此时那个非法状态相当于 ‘0’ ”。
事实上，非法状态只有一个，而且一直没有变过，它的值就是 ∞，那么 0 又是什么呢？
0 是一个合法状态，但在这里， “状态” 的意义有变化，它表示我们没有取前 k - 1 个数中的任何一个数作为子序列，此时最大和当然是零。
你可能会问，这不是矛盾了吗？不是说非法状态就是空的子序列吗？那为什么空的子序列又合法了？存在歧义！
为了更好地解释其原因，我们需要对状态的定义做一些修改：
dp[k][0] 表示在前 k 个数中，我们没有取任何一个数作为子序列；
dp[k][1] 表示在前 k 个数所能构成的非空子序列中，最大的子序列和。
考虑边界条件。
根据定义，显然有 dp[k][0] ≡ 0，而 dp[0][1] = ∞，因为此时并没有任何可以取的数，但我们又要求非空子序列，那么它只能是一个非法状态。
考虑状态转移方程。
dp[k][0] 恒等于 0，不需要做状态转移。
而 dp[k][1] = max(dp[k][1], dp[k][1] + v[k], dp[k][0] + v[k])，即，前 k 个数所构成的最大非空子序列和，可能是前 k - 1 个数所构成的最大非空子序列和，也可能是它们加上当前数之后所构成的和，还可能是仅仅由 v[k] 组成的子序列的和（也就是 v[k] 本身）。
前面所说的 0，指的是 dp[k][0]，它的确是一个合法状态。准确地来说，它是 dp[..][0] 的合法状态，不是 dp[..][1] 的合法状态，自然也就和 dp[..][1] 的非法状态 ∞ 没有任何关系。
将上式化简为：
dp[k][1] = max(dp[k][1], dp[k][1] + v[k], v[k])
又因为我们关注的是非空子序列 dp[..][1]，且 dp[..][0] 恒等于 0，因此可以把第二个维度去掉，变成：dp[k] = max(dp[k], dp[k] + v[k], v[k])
再补上边界条件 dp[0] = ∞
就得到了 4L 的结果！

那么，话说回来，为什么允许空子序列时可以直接写成：
dp[k] = max(dp[k - 1], dp[k - 1] + v[k]), dp[0] = 0
呢？
不妨从状态的定义入手。在这种情况下，我们定义的状态是 “前 k 个元素所能构成的子序列（允许空子序列）中，最大的子序列和”。可见，该定义已经考虑到了空子序列的作用。

talk is cheap，接下来我要用程序来验证上面结论的正确性。

应该没有问题。

我在 4L 楼中楼提到的是这道题：

这里是做了空间优化的，原来的方程是：
dp[i + 1][j + 1] = std::max({curr, dp[i][j] + curr, dp[i + 1][j], dp[i][j + 1]});
我当时就是漏了单独的 curr 这一项。