Leetcode – 62. Unique Paths – Dynamic programming and Combinatorics

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

題目解析

有個m*n的棋盤,左上有個機器人,要前往棋盤右下角(m-1,n-1)。機器人只能往右或往下,求有幾種走法

解法

  1. 針對路線題,我們可以用倒推回來的方式,以右下終點為例,假設要接觸到右下,對於倒數第二步來說只有一種可能。
  2. 使用一個矩形陣列,將每一步都可能性列出來,並用回推的方式疊加回去
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    
    // create matrix
    let matrix = Array(m).fill(1).map(()=>Array(n).fill(1))

    
    for(let i = n - 1 ; i >= 0; i--){
        for(let j = m - 1 ; j >= 0; j--){
            
 
            if(j+1 == m || i+1 == n){
                continue;
            }
            
            matrix[j][i] = matrix[j+1][i] + matrix[j][i+1]
            
        }
    }
    
    
    return matrix[0][0]
    
};

Leave a Comment

發佈留言必須填寫的電子郵件地址不會公開。