62. Unique Paths

// m = 3, n = 7
// 输出: 28

// dp[i][j] 定义为 在 nums1[1..i] 和 nums2[1..j] 的最长公共子序列的长度。
// 动态方程: dp[i][j] = dp[i-1][j] + dp[i][j-1]
// 初始化: `(m+1)*(n+1)`的矩阵dp, 都置为0, 其中dp[1][1] = 1

// ```
// 000
// 01*
// 0**
// ```

/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    let dp = Array.from({length: m+1},()=>Array(n+1).fill(0));

    dp[1][1] = 1;

    for(let i = 1;i<=m;i++){
        for(let j = 1;j<=n;j++){
            if(i===1&&j===1) continue;
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }

    return dp[m][n];
};