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]
    
};