Dynamic Programming

定义状态转移方程的关键在于对状态做出完整表示,举个例子,最长上升子序列问题中,不同的状态是一些子序列,以子序列的最后一项作为划分依据就可以完整表示不同的状态

Greedy Algorithm

贪心策略正确性证明

归纳法

归纳法证明的核心逻辑:证明采用贪心策略执行到任意步数时获得的解都是最优解的一部分

0%