动态规划
动态规划可以看作是 数学归纳法 + 记忆化存储
我们设状态为 dp[i]， bace case dp[0] 可以根据题意快速获得。 其次我们想知道dp[k] 到 dp[k + 1] 的状态转移方程。 这样就能解题了。
- 找不到状态转移方程？ → 说明你的归纳步骤没想清楚（不知道怎么从 k 推到 k+1）。
- 不知道怎么初始化？ → 说明你的Base Case没找对。
- 空间优化（滚动数组）？ → 说明你在归纳步骤中发现，P(k+1) 只依赖于 P(k)，而不依赖于 P(k−100)，所以前面的纸可以扔了。