基本概念
动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法[1]。它的思想就是把一个大的问题进行拆分，细分成一个个小的子问题，且能够从这些小的子问题的解当中推导出原问题的解。
基本性质
- 最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
- 无后效性。即子问题的解一旦确定，就不再改变，不受在这之后、包含它的更大的问题的求解决策影响。
- 子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
实例推演
刚接触动态规划时，很多小伙伴可能会觉得动态规划太难了，让人难以掌握。其实，如果能够了解动态规划的具体推演过程，将对掌握动态规划方法有很大的帮助。下面通过一个简单的例子带大家了解如何找到动态规划方法的。
小猿爬台阶
有n级台阶，小猿每次上一级或者两级，问有多少种走完n级台阶的方法。为了防止溢出，请将结果Mod 1000000007。
给定一个正整数int n，请返回一个数，代表上楼的方式数。保证n小于等于100000。
测试样例：
3
返回：3
数学建模
假设：走到n级台阶的方式数为f(n)。
通过分析，大家可以发现这样一个规律：
- n = 0时，f(0) = 0;
- n = 1时，f(1) = 1;
- n = 2时，f(2) = 2;
- n > 2时，f(n) = f(n - 2) + f(n - 1)。(走到n级台阶的方式数为走到n-1级台阶的方式数与走到n-2级台阶的方式数之和)
递归实现
当发现如上数学规律后，可以很简单的用递归方式实现。这里用java实现代码如下：
public class GoUpstairs {
public int countWays(int n) {
return func1(n);
}
/**
* 暴力搜索
* @param n
* @return
*/
public static int func1(int n) {
System.out.println("计算 n = " + n);
if (n <= 2) {
return n;
}
return (func1(n - 2) + func1(n - 1)) % 1000000007;
}
}
计算f(3)，计算结果如下图所示。
计算 n = 3
计算 n = 1
计算 n = 2
3
计算f(4)，如下图所示。
计算 n = 4
计算 n = 2
计算 n = 3
计算 n = 1
计算 n = 2
5
大家可能会觉得这也太简单了吧！是的，这种递归方法非常简单，但是这种递归方法是暴力计算的，而且会存在大量重复计算，例如在计算f(4)时，会计算两次f(2)。聪明的小伙伴肯定马上就想到了优化方案——既然存在重复计算，那我们把计算过的数据保存下来，下次用到的时候直接取出来用，这样就不必进行重复计算，提高算法效率。这就是我们接下来要讲的优化方案——记忆搜索。
优化一：记忆搜索
我们可以使用一个map将之前计算过的数据保存下来，如果将来用到的话直接取用。java代码如下：
public class GoUpstairs {
public static Map<Integer, Integer> map = new HashMap<>();
public int countWays(int n) {
arrays = new int[n];
for (int i = 0; i < arrays.length; i++) {
arrays[i] = -1;
}
return func2(n);
}
/**
* 记忆搜索
* @param n
* @return
*/
public static int func2(int n) {
if (map.containsKey(n)){
return map.get(n);
}
System.out.println("计算 n = " + n);
if (n <= 2) {
map.put(n, n);
return n;
}
int res = (func2(n - 2) + func2(n - 1)) % 1000000007;
map.put(n, res);
return res;
}
此时，计算f(4)的结果如下：
计算 n = 4
计算 n = 2
计算 n = 3
计算 n = 1
5
记忆搜索的方法是利用空间换时间的策略，通过记录之前的计算结果，避免大量的重复计算。但是这种方法还是有不足之处的——当n比较大的时候可能会导致栈溢出。
当n=100000时，会发生如下异常：
Exception in thread "main" java.lang.StackOverflowError
at java.lang.AbstractStringBuilder.append(AbstractStringBuilder.java:449)
at java.lang.StringBuilder.append(StringBuilder.java:136)
at base.dp.GoUpstairs.func2(GoUpstairs.java:47)
at base.dp.GoUpstairs.func2(GoUpstairs.java:52)
...
优化二：动态规划
我们需要更进一步优化该算法——去除递归结构。其实，通过观察数学规律不难发现，我们只需要一个数组dp，而dp[i]保存的数据就对应f(i)，即爬到i级台阶时有dp[i]种方式。则有
dp[0] = 0;
dp[1] = 1;
dp[1] = 2;
dp[i] = dp[i-1] + dp[i-2];
只需要按顺序遍历计算即可。下面给出该问题的动态规划问题的java代码：
public class GoUpstairs {
public int countWays(int n) {
return func3(n);
}
/**
* 动态规划
* @param n
* @return
*/
public static int func3(int n) {
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[1] = 2;
for (int i = 2; i < n + 1; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
}
return dp[n - 1];
}
}
目前，我们可以发现：其实，记忆搜索和动态规划在本质上是相似的——记忆搜索和动态规划都是将计算过的结果保存下来，避免未来用到时进行重复计算，不同之处在于记忆搜索的方法是不关注计算顺序的，而动态规划却严格规定了计算顺序，因此在某些条件下可以在该基础上继续进行优化。该效果在本文例子中并不明显，笔者会在后续文章中深入讲解。
总结
动态规划的核心思想是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
动态规划的一般步骤[2]
(1)划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。在划分阶段时，注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
(2)确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
(4)寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
一般，只要解决问题的阶段、状态和状态转移决策确定了，就可以写出状态转移方程（包括边界条件）。
实际应用中可以按以下几个简化的步骤进行设计：
（1）分析最优解的性质，并刻画其结构特征。
（2）递归的定义最优解。
（3）以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
（4）根据计算最优值时得到的信息，构造问题的最优解
参考资料
[1] 维基百科-动态规划
[2] 五大常用算法之二：动态规划算法
写在最后
欢迎大家关注我的个人博客复旦猿。
网友评论