导言
动态规划问题一直是算法面试当中的重点和难点，并且动态规划这种通过空间换取时间的算法思想在实际的工作中也会被频繁用到，这篇文章的目的主要是解释清楚 什么是动态规划，还有就是面对一道动态规划问题，一般的 思考步骤 以及其中的注意事项等等，最后通过几道题目将理论和实践结合。
什么是动态规划
如果你还没有听说过动态规划，或者仅仅只有耳闻，或许你可以看看 Quora 上面的这个 回答。
How to explain dynamic
用一句话解释动态规划就是 “记住你之前做过的事”，如果更准确些，其实是 “记住你之前得到的答案”。
我举个大家工作中经常遇到的例子。
在软件开发中，大家经常会遇到一些系统配置的问题，配置不对，系统就会报错，这个时候一般都会去 Google 或者是查阅相关的文档，花了一定的时间将配置修改好。
过了一段时间，去到另一个系统，遇到类似的问题，这个时候已经记不清之前修改过的配置文件长什么样，这个时候有两种方案，一种方案还是去 Google 或者查阅文档，另一种方案是借鉴之前修改过的配置，第一种做法其实是万金油，因为你遇到的任何问题其实都可以去 Google，去查阅相关文件找答案，但是这会花费一定的时间，相比之下，第二种方案肯定会更加地节约时间，但是这个方案是有条件的，条件如下：
- 之前的问题和当前的问题有着关联性，换句话说，之前问题得到的答案可以帮助解决当前问题
- 需要记录之前问题的答案
当然在这个例子中，可以看到的是，上面这两个条件均满足，大可去到之前配置过的文件中，将配置拷贝过来，然后做些细微的调整即可解决当前问题，节约了大量的时间。
不知道你是否从这些描述中发现，对于一个动态规划问题，我们只需要从两个方面考虑，那就是 找出问题之间的联系，以及 记录答案，这里的难点其实是找出问题之间的联系，记录答案只是顺带的事情，利用一些简单的数据结构就可以做到。
思考动态规划问题的四个步骤
一般解决动态规划问题，分为四个步骤，分别是：
- 问题拆解，找到问题之间的具体联系
- 状态定义
- 递推方程推导
- 实现
这里面的重点其实是前两个，如果前两个步骤顺利完成，后面的递推方程推导和代码实现会变得非常简单。
这里还是拿 Quora 上面的例子来讲解，“1+1+1+1+1+1+1+1” 得出答案是 8，那么如何快速计算 “1+ 1+1+1+1+1+1+1+1”，我们首先可以对这个大的问题进行拆解，这里我说的大问题是 9 个 1 相加，这个问题可以拆解成 1 + “8 个 1 相加的答案”，8 个 1 相加继续拆，可以拆解成 1 + “7 个 1 相加的答案”，… 1 + “0 个 1 相加的答案”，到这里，第一个步骤 已经完成。
状态定义 其实是需要思考在解决一个问题的时候我们做了什么事情，然后得出了什么样的答案，对于这个问题，当前问题的答案就是当前的状态，基于上面的问题拆解，你可以发现两个相邻的问题的联系其实是 后一个问题的答案 = 前一个问题的答案 + 1，这里，状态的每次变化就是 +1。
定义好了状态，递推方程就变得非常简单，就是 dp[i] = dp[i - 1] + 1，这里的 dp[i] 记录的是当前问题的答案，也就是当前的状态，dp[i - 1] 记录的是之前相邻的问题的答案，也就是之前的状态，它们之间通过 +1 来实现状态的变更。
最后一步就是实现了，有了状态表示和递推方程，实现这一步上需要重点考虑的其实是初始化，就是用什么样的数据结构，根据问题的要求需要做那些初始值的设定。
public int dpExample(int n) {
// 多开一位用来存放 0 个 1 相加的结果
int[] dp = new int[n + 1];
dp[0] = 0; // 0 个 1 相加等于 0
for (int i = 1; i <= n; ++i) {
dp[i] = dp[i - 1] + 1;
}
return dp[n];
}你可以看到，动态规划这四个步骤其实是相互递进的，状态的定义离不开问题的拆解，递推方程的推导离不开状态的定义，最后的实现代码的核心其实就是递推方程，这中间如果有一个步骤卡壳了则会导致问题无法解决，当问题的复杂程度增加的时候，这里面的思维复杂程度会上升。
来源 | 五分钟学算法
作者 | P.yh
