1、概述
概念
1、动态规划（英语：Dynamic programming，简称DP）通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
2、动态规划常常适用于有重叠子问题性质的问题，动态规划方法所耗时间往往远少于朴素解法。
3、动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
2、暴力递归和动态规划
我们先来看看一个例子，斐波那契数列
暴力递归版本
public static int getFib(int n){
if(n < 0){
return -1;
}else if(n == 0){
return 0;
}else if(n == 1 || n ==2){
return 1;
}else{
return getFib(n - 1) + getFib(n - 2);
}
}
动态规划版本
public static int getFib3(int n){
if(n < 0){
return -1;
}else if(n == 0){
return 0;
}else if (n == 1 || n == 2){
return 1;
}else{
int[] fibAry = new int[n + 1];
fibAry[0] = 0;
fibAry[1] = fibAry[2] = 1;
for(int i = 3; i <= n; i++){
fibAry[i] = fibAry[i - 1] + fibAry[i - 2];
}
return fibAry[n];
}
}
对比以上两个版本，不难发现，递归的过程中，存在大量的重复计算。例如，计算f(5)和计算f(6)时，都重复计算了f(4)，f(3)，f(2)等值的计算。那么如果我们把递归的结果缓存起来，再加之优化，那么就是我们的动态规划。但是，前提是，f(n)的状态只依赖变量n，而不依赖任何的状态。
那么，我们就可以得出结论，当递归公式f(n)，只依赖n，而不依赖任何状态，就可以把整个递归过程，优化为动态规划。
3、例子
那么，以下我们就用两个例子来体会以上的结论。
汉诺塔问题
汉诺塔是典型的递归结果依赖状态的例子，因此无法优化为动态规划。因为每一次的打印，都依赖A柱，B柱，C柱的状态，并且不存在重复的计算，每一次递归都是其需要的结果。
public static void hanoi(int n) {
process(n, "左", "中", "右");
}
/// n代表移动的盘
/// a借助b移动到c
public static void process(int n, String a, String b, String c) {
if (n == 1) {
System.out.println(a + " move " + n + " to " + c);
return;
}
// a借助b把n-1个盘移动到c
process(n - 1, a, c, b);
// 把第n个盘移动到c
System.out.println(a + " move " + n + " to " + c);
// b借助a，把n-1个盘移动到c
process(n - 1, b, a, c);
}
最小路径和问题
求最小路径和，对于一个数组如下
{1, 3, 1},
{1, 5, 1},
{4, 2, 1}
求从左上角到右下角的最小路径和（最小路径为1->3->1->1->1 = 7）。
同样地，我们先写出暴力递归版本。对于每一个节点，其选择总是有两个下移动，或者向右移动，然后取路径和较小的作为结果。那么以上就是我们的递归方程
public static int minPathSum(int[][] matric, int lx, int ly) {
if (lx == matric.length - 1 && ly == matric[0].length - 1) {
return matric[lx][ly];
}else if(lx == matric.length - 1) {
// 不能在往下走了
return minPathSum(matric, lx, ly + 1) + matric[lx][ly];
}else if (ly == matric[0].length - 1) {
// 不能再往右走了
return minPathSum(matric, lx + 1, ly) + matric[lx][ly];
}else {
// 分别求往右走，往下走时路径和，然后去最小的
int right = minPathSum(matric, lx + 1, ly);
int bottom = minPathSum(matric, lx, ly + 1);
return Math.min(right, bottom) + matric[lx][ly];
}
}
同样地，我们不难发现其递归过程不依赖状态，且也进行了大量的重复计算。那么我们就将其改为动态规划版本
public static int minPathSum2(int[][] matric, int lx, int ly) {
int N = matric.length;
int M = matric[0].length;
// path[i][j] 表示从左上角 走到 matric[i][j] 的最小路径和
int[][] path = new int[N][M];
path[lx][ly] = matric[lx][ly];
// 填充第一行
for(int i = 1; i < N; i++) {
path[i][0] = path[i - 1][0] + matric[i][0];
}
// 填充第一列
for(int i = 1; i < M; i++) {
path[0][i] = path[0][i - 1] + matric[0][i];
}
// 开始填数字
for(int i = 1 ; i < N; i++) {
for (int j = 1; j < M; j++) {
path[i][j] = Math.min(path[i - 1][j], path[i][j - 1]) + matric[i][j];
}
}
return path[N - 1][M - 1];
}
规划图如下:
| 1 | 4 | 5 |
|---|---|---|
| 2 | 7 | 6 |
| 6 | 8 | 7 |
4、总结
由于暴力递归存在着大量重复计算，而动态规划其实是一种由经验积累，为解决暴力递归而产生的优化技巧。因此，暴力递归时方法的始解，若对每一道dp都能先想到暴力递归，那么在其基础上，我们就可以进行dp优化了。当然，能一开始想到dp的方法当然是最好啦，后面一篇，我将介绍常见的dp算法
