对于一个半路出家的前端从业者，对于算法啥的还是比较薄弱的，自从上次公司一个新需求用到了动态规划算法，深深感觉到了动态规划算法的强大，这里记录几个复杂度循序渐进的动态规划案例及其讲解以及一点点扩展。

什么是动态规划？

动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。它将问题拆分成小问题，并从解决小问题作为起点，从而最终解决问题。

接下来我们从简单的例子看起，感受一下动态规划算法的魅力。

问题一：爬梯子问题

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2

输出： 2

解释： 有两种方法可以爬到楼顶。

a、1 阶 + 1 阶

b、2 阶

示例 2：

输入： 3

输出： 3

解释： 有三种方法可以爬到楼顶。

a、1 阶 + 1 阶 + 1 阶

b、1 阶 + 2 阶

c、2 阶 + 1 阶

走1阶台阶只有一种走法，但是走2阶台阶有两种走法（如示例1），如果n是双数，我们可以凑成m个2级台阶，每个m都有两种走法，如果n是单数，那么我们可以凑成m个2级台阶加上一个1级台阶，这样就似乎于一个排列组合题目了，但是开销貌似比较大。

如何将整个问题拆分成一个一个的小问题呢？

这个时候使用动态规划就很有用，因为这个问题其实是由一个很简单的小问题组成的。

观察这种小问题，简单地我们可以采用首位或者中间态进行一次分析，比如我们从最终态进行分析：

走N阶台阶，最后一步必定是1步或者2步到达。

那么N阶台阶的走法不就相当于最后走一步和最后走两步的走法的总和吗？换一种方式来说，我们取一个中间态：如果总共有3级台阶，3级台阶的走法只会存在两种大的可能：走了1阶台阶+走两步、走了两级台阶+走一步，即3级台阶的所有走法就是走了1阶台阶的走法加上走了2阶台阶的走法，而1阶台阶的走法只有一种，2阶台阶的走法有2种，所有3阶台阶的走法有3种,我们使用一种更通用的方式进行表达的话就是所谓的状态转换方程：

ways[n] = ways[n-1] + ways[n-2]

有了这个公式，我们就可以使用迭代来完成整个过程，寻求到最终的ways[n]的值了，迭代的开始即我们已知的确定条件：一阶台阶只有一种走法：ways[1]=1、两阶台阶有两种走法：ways[2]=2，代码如下：

function climbStairs(n) {
	if (n === 1 || n === 2) {
		return n;
	}

	var ways = [];
	ways[0] = 1;
	ways[1] = 2;

	for(var i=2; i<n; i++){
		ways[i]=ways[i-1] + ways[i-2];
	}

	return ways[n-1];
}

梳理一下基本流程：

1、从一个现实方案中找到状态转换的特有规律

2、从特有规律中提取出状态转换方程

3、找到状态转换方程的迭代初始值（确定值）

4、解决问题

我们接着看下一个问题

问题二：所有路径问题

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2

输出: 3

解释:

从左上角开始，总共有 3 条路径可以到达右下角。

a、向右 -> 向右 -> 向下

b、向右 -> 向下 -> 向右

c、向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3

输出: 28

相信沿用问题一的套路很多人已经知道该怎么办了，从一个二维数组的左上（0，0）走到右下（m,n）有多少种走法，且只能往右和往下走，那么如果要走到（m,n），那么我们的上一步只能是（m-1,n）或者（m,n-1），所以走到（m,n）的所有走法就是走到（m-1,n）的所有走法+走到(m,n-1)的所有走法，即可以得到状态转换方程：

ways[m][n] = ways[m-1][n] + ways[m][n-1]

但是，这个问题还有一些其他的问题限制需要我们考虑到，即走到两侧的时候，只会有一个方向的走法，（上方只会有ways[m-1][n]一个方式，左侧只会有ways[m][n-1]一个方式）即下图：

我们需要对这两种方式进行限制，在这里我在外围再扩展了一圈，将整个方格扩展为**(m+1)*(n+1)**的方格，来避开限制，当然也可以直接限制（后续会讲到），但是将其所有的值都设置为0，即相当于设置了限制。

实现代码：

function countPaths(m, n) {
	var ways = new Array(m+1);
	for (var i=0; i<=m; i++) {
		ways[i] = new Array(n+1);
	}

	//上方扩展一行，使其值为0
	for(var i=0; i<=n; i++){
		ways[0][i] = 0;
	}

	//边上扩展一列，使其值为0
	for(var j=0; j<=m; j++){
		ways[j][0] = 0;
	}

	//设置初始值，起点走法为1，只能一步一步走
	ways[1][1]=1;

	for (var a=1; a<=m; a++) {
		for (var b=1; b<=n; b++) {
			if (a===1 && b===1) {
				continue;
			}
			//套用状态转换方程
			ways[a][b] = ways[a][b-1] + ways[a-1][b];
		}
	}

	return ways[m][n];
}

问题三：最小路径和

给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例:

输入:

[
   [1,3,1],
   [1,5,1],
   [4,2,1]
]

输出: 7

解释: 因为路径 1→3→1→1→1 的总和最小。

这个问题与问题二及其相似，但是其涉及到一个最优解的问题，现在每一个点都有一个类似权重的值，我们要使这个值最小，其实用问题二的想法，我们很快就能得到答案：走到(m,n)只能从(m-1,n)和(m,n-1)两个地方走过来，那么要保证(m,n)的权重最小，那么我们只需要选择走到(m-1,n)和（m，n-1）权重较小的那一边即可，那么我们就可以得到新的状态转移方程：

sum[m][n] = MIN(sum[m-1][n], sum[m][n-1]) + table[m][n]

即走到当前点的权重=走到前一步权重的较小值+当前点的权重，并且该问题也有针对边上元素的特殊处理。

实现代码：

function minPathSum(grid) {
	if (grid && grid.length) {
		//权重存储数组
		var sum = new Array(grid.length);
		for (var i=0; i<grid[0].length; i++) {
			sum[i] = new Array(grid[0].length);
		}

		//起点初始权重确定值
		sum[0][0]=grid[0][0];

		for (var i=0; i<grid.length; i++) {
			for (var j=0; j<grid[0].length; j++) {
				if (i===0 && j===0) {
					continue;
				}
				//边上的权重处理
				if (i-1<0) {
					sum[i][j] = sum[i][j-1] + grid[i][j];
				} else if(j-1<0) {
					sum[i][j] = sum[i-1][j] + grid[i][j];
				} else {
					sum[i][j] = Math.min(sum[i-1][j], sum[i][j-1]) + grid[i][j];
				}
			}
		}

		return sum[grid.length-1][grid[0].length-1];
	} else {
		throw new Error('Fuck!');
		return ;
	}
}

可能有朋友会说上面的例子虽然讲解了动态规划的基本思路，但是这种例子在工作中基本不回出现，最后再记录一个工作中可能会遇到的问题。

问题四：所有字母组合问题

假设我们给定字母一批字母，在允许任意字母顺序的情况下，我们可以得到多少种长度雨输入字母长度相等的字母组合呢？

示例 1:

输入："a"

输出："a"

示例 2:

输入："ab"

输出："ab", "ba"

示例 3:

输入："abc"

输出："abc", "acb", "bac", "bca", "cab", "cba"

实现代码：

function anagrams (str) {
  if (str.length <= 2) return str.length === 2 ? [str, str[1] + str[0]] : [str];
  return str.split('').reduce((acc, letter, i) =>
    acc.concat(anagrams(str.slice(0, i) + str.slice(i + 1)).map(val => letter + val)), []);
};

参考链接：

从实例中了解动态规划的基本思想

详解动态规划01背包问题

详解动态规划最少硬币找零问题

详解动态规划最长公共子序列