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算法