每当大家谈起动态规划这个词，不明觉厉。想趁着这次技术分享的机会，了解下动态规划到底是什么小天使。

动态规划概念

动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

它不是某一种具体的算法，而是一种算法思想：若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。

应用这种算法思想解决问题的可行性，对子问题与原问题的关系，以及子问题之间的关系这两方面有一些要求，它们分别对应了最优子结构和重复子问题。

最优子结构

最优子结构规定的是子问题与原问题的关系

动态规划要解决的都是一些问题的最优解，即从很多解决方案中找出最优的一个。当我们在求一个问题最优解的时候，我们可以把这些问题分解成多个子问题，然后递归地找到每个子问题的最优解，最后通过一定的数学方法对各个子问题的最优解进行组合得到最终的结果。总结来说就是一个问题的最优解是由它的各个子问题的最优解决定的。看图说话：

将子问题的解进行组合可以得到原问题的解是动态规划可行性的关键，在解题中一般用状态转移方程描述这种组合。

例如原问题的解为f(n)，fn(n)也叫状态，不同选择可能对应不同的子问题或不同的组合方式。例如n = 2k和n - 2k+1对应了原问题n上的不同选择，分别对应了不同的子问题和组合方式。找到了最优子结构，也就能推导出一个状态转移方程f(n)，通过状态转移方程，我们也能很快的写出问题的解法。

重复子问题

重复子问题规定的是子问题与子问题的关系

当我们在递归寻找每个子问题的最优解的时候，有可能会遇到一些更小的子问题，而且这些子问题会重叠的出现在子问题里，出现这样的情况，会有很多重复的计算。动态规划可以保证每个重复的子问题只会被求解一次。当重复的问题很多时，动态规划可以减少很多重复的计算。如果没有出现重复子问题，就没必要用动态规划，直接普通递归就可以。

例如斐波那契的动态转移方程是f(n) = f(n - 1) + f(n - 2)。在求f(5)时，需要先求子问题f(4)和f(3)，得到结果后再组合成原问题f(5)的解。递归地求f(4)时，又要先求子问题f(3)和f(2)，这里的f(3)与求f(5)时的子问题重复了。

动态规划核心：找出子问题以及子问题与原问题之间的关系

找到了子问题以及子问题与原问题的关系，就能递归地求解子问题了。但重叠的子问题使得直接递归会多很多重复的计算，于是就想到记忆化递归法：若能事先确定子问题的范围就可以建表存储子问题的答案

以上是动态规划的概念，但到了做题环节，还是摸不着头脑，不知道如何下手。动态规划无疑就是利用历史记录，来避免我们的重复计算。而这些历史记录，我们得需要一些变量来保存，一般是用一维和二维数组来保存。下面我们先来讲下动态规划题很重要的三个步骤。

动态规划解题步骤

第一步骤：定义数组元素的含义。 上面说了，我们会用一个数组，来保存历史数据。假设定义一个一维数组dp，那dp[n]代表什么意思呢

第二步骤：找出数组元素之间的关系式。当我们要计算dp[n]，是可以利用历史数据dp[n-1]，dp[n-2]，，，dp[1]来推出新的元素值，例如dp[n] = dp[n-1] + dp[n-2]。这个就是他们的关系式了，而这一步，也是最难的一步。后面我会讲几种类型的题来说。

第三步骤：找出初始值。我们知道了数组元素之间的关系式，例如dp = dp[n-1]+dp[n-2]，但我们需要知道初始值，因为一直往前推的话，会有dp[3] = dp[2] + dp[1]，而dp[2]和dp[1]不能再分解，所以我们需要直接获得dp[2]和dp[1]的值，而这就是所谓的初始值。

有了初始值，以及数组元素之间的表达式，我们就可以求出dp[n]，而dp[n]的含义是由你来定义的，你想求什么，你就定义它是什么。这样，这道题就解出来了。

如果上面听的不太懂的话，没事，我会按照这个步骤给大家讲解两道例题。

案例讲解

三步问题

题目描述：有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。

示例1：输入n = 3
那上3阶台阶的话，有多少种上楼梯的方式呢，我们来枚举下：
1、先上1阶，再上1阶，再上1阶
2、先上1阶，再上2阶
3、先上2阶，再上1阶
4、先上3阶
输出：4

示例2：输入n = 5
那上5阶台阶的话，有多少种上楼梯的方式呢。
1、先上1阶，再上1阶，再上1阶，再上1阶，再上1阶
2、先上1阶，再上2阶，再上2阶
3、先上2阶，再上3阶
...就不一一枚举了
输出：13

这道题怎么解呢？按这个步骤来吧

第一步骤：定义数组元素的含义。我们的问题是小孩上n阶台阶有多少种上法，那我们就定义dp[n]：这个小孩上n阶台阶总共有dp[n]种上法

第二步骤：找出数组元素之间的关系式。动态规划的题，是把规模较大的问题分成规模较小的问题，然后由小的问题推导出大的问题。dp[n]的规模是n，比它规模小的是n-1，n-2，n-2，也就是说，dp[n]一定会和dp[n-1]，dp[n-2]…存在某种关系的。我们要找出他们的关系。对于这道题，由于小孩一次可以上1阶、2阶、3阶，所以上n阶台阶总共有3种方式，一种是从第n-1阶跳上来，另一种是从第n-2阶跳上来，最后一种是从第n-3阶跳上来。得出关系式：dp[n] = dp[n-1] + dp[n-2] + dp[n-3]

第三步骤：找出初始值。由于数组下标不能是负数，所以我们给出初始值dp[0]，dp[1]，dp[2]，dp[3]

具体代码实现

/**
 * @param {number} n
 * @return {number}
 */
var waysToStep = function(n) {
    var dp = new Array(n);
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    for(var j = 4; j <= n; j++) {
        dp[j] = (dp[j - 1] + dp[j - 2] + dp[j - 3]) % 1000000007; 
    }
    return dp[n];
};

不同路径

题目描述：一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？

示例输入：m =3, n = 2
从左上角开始，总共有3条路径可以到达右下角。
1、向右 —> 向右 —> 向下
2、向下 —> 向右 —> 向右
3、向右 —> 向下 —> 向右
输出：3

还是老样子，三个步骤来解决。

第一步骤：定义数组元素的含义。我们的问题是从左上角到右下角一共有多少种路径，那我们就定义dp[i][j]：当机器人从左上角走到（i, j）这个位置时，一共有dp[i][j]种路径。那么dp[m - 1][n - 1]就是我们要的答案了。

第二步骤：找出数组元素之间的关系式。想象一下机器人怎么才能到达（i, j）这个位置，由于机器人只能向下或者向右走，所以有两种方式，一种是从（i-1, j）这个位置走一步到达，一种是从（i, j-1）这个位置走一步到达

第三步骤：找出初始值。由于数组下标不能是负数，所以我们给出最上边一行和最左边一列的初始值dp[0…m-1][0] = 1、dp[0][0…n-1] = 1

具体代码实现

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    var dp = new Array(m).fill(0);
    dp = dp.map(item => new Array(n).fill(0));
    // 初始值，最上面一排只能一直往右走
    for (var a = 0; a < m; a++) {
        dp[a][0] = 1;
    }
    // 初始值，最左边一排只能一直往下走
    for (var b = 0; b < n; b++) {
        dp[0][b] = 1;
    }
    for (var i = 1; i < m; i++) {
        for (var j = 1; j < n; j++) {
            dp[i][j] = dp [i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
};

以上两道题都是不怎么难的入门题。而动态规划远比我想象中复杂的多，需要慢慢持续学习。不如我们来看下它的类别。

感兴趣的同学可以按照这个类别深入研究～

动态规划概念
1. 最优子结构
2. 重复子问题
动态规划解题步骤
案例讲解
1. 三步问题
2. 不同路径