减少转移

有一种优化 $dp$ 的方式是减少转移，即我们发现某些转移就是不优秀的，然后扔掉，但是又怕多种转移扔掉后，相互作用，把答案扔掉了怎么办。

一种简单的证明方法是：

证明答案可以用当前 $dp$ 生成，即用现在的转移生成的的集合一定是原来转移集合的子集，答案一定不优于原答案，因此只要证明存在一种原答案的方案使得能够用这种转移生成就行。

减少状态

一种经典的 $dp$ 优化是我们记录二元组 $(x,y)$ ，发现 $y$ 单调，所以用 $f[x]$ 记录 $y$ 的最值。

但是这怎么用 $dp$ 语言证明呢？

我的建议是一种类似归纳的证法，从小到大，证明每个被丢掉的状态答案都一定不优于没被丢掉的状态，所以答案一定出在保留状态所能转移出来的答案中，即答案一定在保留状态能转移出来的集合中。

举个例子，我们证明 $(x,1)$ 根据现有转移所产生的的答案严格不优于 $(x,2)$ ，所以答案一定产生于 $(x,2)$ 转移出来的状态中，所以只关心 $(x,f[x])$ 转移出来的结果，然后再证明 $(x+1,f[x+1])$ ，以此类推，就可以证明该 $dp$ 的正确性了。（之所以要从小打大类似归纳，是因为我们在证明 $(x+1)$ 的时候，实际上就已经只在丢 $(x,f[x])$ 转移出来的没用的状态，那些之前就丢到的状态，甚至都没法转移，自然讨论 $x+1$ 的时候不会带上他们）

既减少转移又减少状态

这个时候要小心了，有可能减少转移的前提是存在某些状态，或者减少状态的前提是存在某些转移。

一种常见的流程是：先证明减少转移的正确性，再在减少过的转移下（即新问题下），证明减少状态的正确性，或者反过来。即先证明一个，再证明另外一个，但是注意后一个是基于前面一个已经实现的新问题上的。

总结

总之，上面说的证明思路总结下来就一条：

证明扔掉的部分答案小于等于留存的，从而证明答案一定出现在留存状态的集合中。（因为是减少状态或者转移，只能是原来状态的子集，因此答案只会变劣，不会变优，证明单边等号即可）