【有书共读】《算法与数据结构题目最优解》（在线编程题总结4）

该书第四章——《动态规划与递归》，这部分是秋招面试与笔试中的重中之重，有必要好好掌握，我已总结到个人的CSDN博客，详见：https://blog.csdn.net/zichen_ziqi/article/details/82184495。具体内容如下：

O、求解方法：阶段 + 状态变量 + 状态转移方程 + 边界条件

（1）划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。

（2）确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。

（3）确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两段各状态之间的关系来确定决策。

（4）寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

一、问题总结（详见以上链接）

1、硬币问题

2、爬楼梯问题（青蛙跳台问题）

3、装箱问题与背包问题

4、最大递增子序列问题（最长上升子序列问题）

5、最长公共子序列问题

6、最长公共子串问题

7、最大连续子序列求和问题（最大子串求和问题）

8、股票收益最大化（一次交易、多次交易与最多两次交易）