动态规划算法，js实现，图解执行原理_动态规划原理 动图

定义

动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。
在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最 优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

典型案例实现逻辑

案例1，LeetCode 62、不同路径

LeetCode 62、不同路径

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

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

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

输入：m = 3, n = 7
输出：28
1
2

题解代码

var uniquePaths = function(m, n) {
        var grid = Array.from({length: m}, function (){
            return Array(n).fill(0)
        })
        for(var i = 0; i < m; i++)
            for(var j = 0; j < n; j++)
                grid[i][j] = i === 0 || j === 0 ? 1 : grid[i - 1][j] + grid[i][j - 1]
        return grid[m - 1][n - 1]
    };
    console.log(uniquePaths(3,7))
1
2
3
4
5
6
7
8
9
10

结果

过程

案例2，LeetCode 63、不同路径Ⅱ

LeetCode 63、不同路径Ⅱ

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

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

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：
3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右
1
2
3
4
5
6
7

题解代码

    var uniquePathsWithObstacles = function(obstacleGrid) {
        var n = obstacleGrid.length;
        var m = obstacleGrid[0].length;
        var result = Array(m).fill(0);
        result[0] = 1;
        for(var i = 0;i < n;i++){
            for(var j = 0;j < m;j++){
                if(obstacleGrid[i][j] === 1){
                    result[j] = 0;
                }else if(j !== 0){
                    result[j] += result[j-1];
                }
            }
        }
        return result[m-1];
    };
    console.log(uniquePathsWithObstacles([[1,0,0],[0,1,0],[0,0,0]]))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

结果

过程

案例3，LeetCode 64、最小路径和

LeetCode 64、最小路径和

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

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

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。
1
2
3

题解代码

var minPathSum = function(grid) {
        for( let i = 0 ; i < grid.length ; i ++ ){
            for ( let j = 0 ; j < grid[i].length ; j ++ ){
                grid[i][j] += !i ? ( j ? grid[i][j-1] : 0 ) : ( j ? Math.min(grid[i][j-1],grid[i-1][j]) : grid[i-1][j] )
            }
        }
        return grid.pop().pop()
    }
    console.log(minPathSum([[1,3,1],[1,5,1],[4,2,1]]))
1
2
3
4
5
6
7
8
9

结果

过程