一、定义和举例

1.1 定义

  • 什么是动态规划？百度是这么说的：动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。20世纪50年代初，美国数学家贝尔曼（R.Bellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理，从而创立了动态规划。动态规划的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

  • 很好，说了等于没说。当然了，这只是最粗略的概括，再深入探究的话，涉及到的内容我也搞不清楚（读大学时有修过运筹学这门学科，但是忘得差不多了）。 这里不深入讨论数学方面的知识，那么动态规划到底是什么意思呢？通俗一点的说：

  • 动态规划就是从下往上(从前向后)阶梯型求解数值。还是不明白？

1.2 举个栗子

爬楼梯

大家都有过爬楼梯的经历，你是会一次上一个台阶还是一次上两个台阶呢？或者挑战一下自己，跨三阶甚至四阶？
现在我们来分析一下这个场景，并加一点限制：

  • 张三现在来爬楼梯了，他腿比较短，一次只能上一个或者两个台阶，不过还好，他要上的楼梯只有三阶，那他会有几种走法？
    聪明的你看都看出来了，这还不简单？
  1. 走一阶 -> 走一阶 -> 走一阶
  2. 走一阶 -> 走两阶
  3. 走两阶 -> 走一阶

OK！爬上去了，这种楼层很低的情况确实很简单。那换种情况，很不幸，张三今天要去爬峨眉山，峨眉山从五显岗到金顶大概有22000多层阶梯，你还能看出来张三共有多少种走法吗？当然不行。
那我们先从简单的开始，张三假如再往上多爬一层，爬到第四层阶梯有几种爬法？这时候心算能力差一点的同学可能需要用小本本来计算一下所有情况了，我们列举一下：

  1. 走一阶 -> 走一阶 -> 走一阶 -> 走一阶
  2. 走一阶 -> 走两阶 -> 走一阶
  3. 走一阶 -> 走一阶 -> 走两阶
  4. 走两阶 -> 走一阶 -> 走一阶
  5. 走两阶 -> 走两阶

好！停，可以预见的是，阶数如果再加大，枚举将变得不现实，数量太多不仅容易重复记录还容易漏数。所以我们现在只能换个思路。
以下就是动态规划的核心思想了：

张三如果要走到四层，他必须干什么？没错，他必须先走到第三层或者先到第二层。

欸！对哎，可是那又怎么样呢？那可太重要了！
我们可以得出一个很重要的结论：

  • 张三走到第四层的所有方法是走到第三层的所有方法加上走到第二层的所有方法。
    再扩展一下
  • 张三走到第三层的所有方法是走到第二层的所有方法加上走到第一层的所有方法。
  • … 第五层 … 是 … 第四层 … 加上 … 第三层 …。
  • … 第n层 … 是 … 第n-1层 … 加上 … 第n-2层 …。

发现规律了吗？没错，一句话总结就是：

张三后续做的决策都会受到前面所做决策的影响！

1.3 小结一下

可能有过算法基础的同学觉得这个上面的分析好像有点似曾相识啊，有点像那个什么斐波那契数列，还有点像递归思想。
这里就不讨论递归是什么了，但是需要知道，递归不等于动态规划，他们的思想刚好相反，前面说过，动态规划是从下往上(从前向后)阶梯型求解数值。而递归是从上往下(从后向前)阶梯型求解数值。
更通俗一点的说：

  • 递归是先解决大问题，再解决小问题

  • 动态规划是先解决小问题，再解决大问题

  • 下面是递归和动态规划的代码示例，有兴趣的同学可以琢磨一下

1
2
3
4
5
6
7
8
9
//递归
class Ra {
    int factorial(int n) {
        if (n == 0 || n == 1) {
            return 1;
        }
        return n * factorial(n - 1);   // 从最大的数字开始考虑
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//动态规划
class Dp {
    int factorial(int n) {
        int dp = new int[100];// 动态数组的含义：里面放着从 1-n 每一个数字的阶乘
        dp[0] = 1;
        if (n == 0) {
            return dp[0];
        }
        for (
                int i = 1;
                i <= n; i++) // 从最小的数字开始考虑，将所有的结果放在数组中
        {
            dp[i] = i * dp[i - 1];
        }
        return dp[n];
    }
}

二、解决问题

2.1 定义数组元素含义

  • 首先我们重新梳理一下问题：
    假设张三正在爬楼梯，需要 n 阶才能到达楼顶。
    每次可以爬 1 或 2 个台阶。他会有多少种不同的方法可以爬到楼顶呢？

  • 有了明确的问题，再加上前面的分析之后，我们进行第一步：定义数组元素含义。
    我们先来定义一个数组dp[n]，他代表爬到第n阶楼梯所用的方法数，也就是我们要求的结果。

1
2
3
4
5
class Solution {
    /*  省略  */
    int[] dp = new int[n + 1];//dp[n]即为我们想要的结果
    /*  省略  */
}

2.2 找出数组元素之间的关系式（状态转移方程）

  • 这是最难的一步，好在前面我们已经分析出来了，还记得吗？

  • … 第n层 … 是 … 第n-1层 … 加上 … 第n-2层 …。
    所以我们得出了状态转移方程：

  • dp[n] = dp[n - 1] + dp[n - 2];

2.3 找出初始值

  • 有的同学已经发现，上面的方程可能出现数组越界的问题。
    没错，动态规划都会存在初始值，不需要或者不能用状态转移方程得出；
    因此，我们第三步要做的就是找出这些初始值。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int climbStairs(int n) {
        /*  省略  */
        int[] dp = new int[n + 1];//dp[n]即为我们想要的结果
        /*  省略  */
        //找出初始值
        dp[1] = 1;
        dp[2] = 2;
        /*  省略  */
    }
}

好！准备工作已经完成，我们现在可以写出最后的算法了，相关的注释我会写在代码中：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int climbStairs(int n) {
        //分析
        //爬到n层可以爬到第n-1层再爬一步到n，或者爬到n-2再一次爬两步到n
        //假设dp[n]代表爬到第n层可以用的方法数，那么dp[n]=dp[n-1]+dp[n-2];
        //dp[3]=dp[1]+dp[2];
        //dp[1]和dp[2]是初始值，无法通过公式计算

        //创建一个数组来保存历史数据
        int[] dp = new int[n + 1];
        //排除两种初始情况
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

三、总结

  • 以上就是最经典的动态规划入门题目：《爬楼梯》的一个简单分析和对应的解法。
    当然了，解法不止这一种，就动态规划入门而言，我觉得这种解法相对容易理解一些。