leetcode-------不同路径(JavaScript解法)

谁借莪１个温暖的怀抱￠ 2022-12-01 14:12 170阅读 0赞

#### 一、题目描述 ####

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

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

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

#### 二、示例 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70_pic_center]

#### 三、解题思路 ####

这个题目我选择用动态规划，这个的动态方程也比较简单，从最后一个入手开始，只能从上或者左边走的话，就可以是上和左的和，一次类推遍历循环。这里要注意的是第一行和第一列要进行初始化  
dp\[i\]\[0\] = 1,dp\[0\]\[j\] = 1.

#### 四、代码 ####

/** * @param {number} m * @param {number} n * @return {number} */
    var uniquePaths = function(m, n) { 
        var dp = new Array(m)
        for(let i = 0 ; i < m ; i++)
        { 
            dp[i] = new Array(m);
            dp[i][0] = 1
        }
        for(let r = 0 ; r < n ; r++){ 
            dp[0][r]= 1
        }
        for(let x = 1 ; x < m ; x++){ 
            for(let y = 1 ; y < n ; y++){ 
                dp[x][y] = dp[x-1][y] + dp[x][y-1]
            }
        }
        return dp[m-1][n-1]
    
    };

#### 五、运行结果 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70_pic_center 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/23ee8f801c6c4844bd7ed699791c9664.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODk3OTc4_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/2c8288ee7a2c47a8a5e5a4e902937e4a.png