动态规划的思想 它的思想就是把一个大的问题进行拆分，细分成一个个小的子问题，且能够从这些小的子问题的解当中推导出原问题的解。同时还需要满足以下两个重要性质才能进行动态规划
最优子结构性: 既所拆分的子问题的解是最优解。 子问题重叠性质: 既在求解的过程当中，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率 动态规划实例1：斐波拉契数列 计算斐波那契数列：斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368…这个数列从第3项开始，每一项都等于前两项之和。 代码如下：
//动态规划实现斐波拉契数列 function feiBoLaQie(n) { //创建一个数组，用于存放斐波拉契数组的数值 let val = []; //将数组初始化，将数组的每一项都置为0 for(let i =0 ;i<=n;i++){ val[i] = 0; } if (n==1 || n==2){ return 1; } else{ val[1] = 1; val[2] = 2; for (let j =3; j<=n;j++){ val[j] = val[j-1] + val[j-2]; } } return val[n-1]; } console.log(feiBoLaQie(40));//102334155动态规划实例2：爬梯子问题 假设你正在爬楼梯。需要 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级台阶，这样就似乎于一个排列组合题目了，但是开销貌似比较大。 代码如下：
//爬楼梯问题 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]; } console.log(climbStairs(3));//3动态规划实例3：所有路径问题 一个机器人位于一个 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]一个方式）即下图：
//动态规划实现所有路径问题 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]; } console.log(countPaths(3,2));//3 console.log(countPaths(7,3));//28动态规划实例4：最小路径和 给定一个包含非负整数的 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 ; } } var grid = [ [1,3,1], [1,5,1], [4,2,1] ] console.log(minPathSum(grid));//7