【js算法】动态归回dp----不同路径（详细解答，一看就懂）

本文主要是介绍【js算法】动态归回dp----不同路径（详细解答，一看就懂），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

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

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

【思路】
最后的终点有两条路径 从上边一格进入或者从左边 一格进入；
给每一个格子一格值，表示走入这个格子的走法，那么， 最后一个格子的走法 = 上边一个格子的走法 + 左边一格格子的走法
找到动态规划的公式之后

【代码】

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    if(m===1&&n===1){return 1}; //如果是一行一列的话就只有一种走法
    let data=[]; rows=[0]; //data表示存储值的容器；rows表示每一行对应列初始值
    for(let i=0; i<n-1; i++){
        rows.push(1);//n 表示的是有多少列，这一步表示的是给第一行的每一列一个初始值1
    }
    data.push(rows) //然后将第一行添加到这个数据容器中
    for(let i=0; i<m-1; i++){
        data.push([1]) //m表示的是 有多少行，这一步表示的是给这个容器的第一列添加m-1行数据，对应的，每一行的数据都是一个数组，数组中的每一项的值对应的是相应行相应列的“走法”
    }
    //下边是一个模拟的 m=3,n=4的数据
    //data = [
	//	[0,1,1,1,1],
	//	[1],
	//	[1],
	//  [1],
	//]
    for(let i=1; i<m; i++){
        for(let j=1; j<n; j++){
            data[i][j]=data[i-1][j]+data[i][j-1] //对数据容器进行遍历，从第一行第一列开始（显然由上可得，只有一种）
            //m 表示行， m=1的时候，第j列的值应该是 data[1][j] = data[0][j] + data[1][j-1] 
            // 假设此时 j=1, data[1][1] = data[0][1] + data[1][0] = 1 + 1 = 2
        }
    }
    return data[m-1][n-1]
    // 至于为什么最终返回的是 [m-1][n-1],可以看上边模拟出来的data容器中的数据，m表示行，n表示列，在模拟的数据容器中，用户需要的数据是data[m-1][n-1]
};

这篇关于【js算法】动态归回dp----不同路径（详细解答，一看就懂）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！