Interesting dynamic programming.

一、理论基础和模板

Dynamic Programming的核心理论源于运筹学领域；在动态规划中存在一些重要的概念,例如,重叠子问题的概念,以及最优子结构的概念,还有状态转移方程的相关定义等

• 重叠子问题(Overlapping Subproblems)

具体问题可以通过解决其相关子问题来实现解决方案；例如，在斐波那契数列中，F(n)可由前两项之和进行计算得出。

• 最优子结构特性(Optimal Substructure Property)

如果问题的最佳解答可以通过子问题的最佳解答获取，则说明该问题具有最优子结构特性。

• 状态(state)与转移(transition)方程

1.1 解决一个动态规划问题的4步曲

• 步骤一：利用「重叠子问题」与「最优子结构特性」这两个关键特征来判断目标问题是否具备动态规划求解的可能性。
• 步骤二：构建一个状态模型，并明确最少数量的状态变量及其对应的索引含义。
• 步骤三：建立状态转移关系式并初始化初始条件。
• 步骤四：采用表格法或备忘录法以优化计算资源消耗（明确地定义状态模型）。

其中最为复杂的是第二步以及第三步，在分析重叠子问题以及最优子结构时，请指导如何定义dp的含义以及状态转移方程；在探索递推关系时，请指导如何将当前状态与前一状态或其他相关状态联系起来。对于二维d