题解 | #走方格的方案数#

let line;
while(line = readline()) {
    let [n, m] = line.split(' ').map(e => parseInt(e));
    console.log(solution(n, m));
}
/**
 *动态规划求解：
 * dp[i-1][j-1] = dp[i-1][j] + dp[i][j-1];
 * 例如：2x2网格
   (6)----(3)----(1)
   |       |      |
 * (3)----(2)----(1)
   |       |      |
   (1)----(1)----(1)
   每个顶点标注其到达网格右下角的方案总数（括弧里面的数）
   依题意最后一行和最后一列顶点方案数都是1
   其它顶点的方案数等于右边和下面直接相邻的顶点方案数之和
   即：
   第(i-1，j-1)结点的方案数计算如下图：
    i-1,j-1 (A)----(B) i-1, j
            |       |
    i, j-1  (C)----(D) i, j
    A = B + C
 */
function solution(n, m) {
    let dp = new Array(n+1).fill(0).map(() => new Array(m+1));
    for(let i = 0;  i <= n; i++) {
        dp[i][m] = 1;
    }
    for(let j = 0;  j <= m; j++) {
        dp[n][j] = 1;
    }   
    for(let i = n; i > 0; i--) {
        for(let j = m; j > 0; j--) {
            dp[i-1][j-1] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[0][0];    
}