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

const rl = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout,
});

/**
 * dp 五步：
 *
 * 1. dp 数组的含义和下标的定义
 * dp[m][n] = ? , m 是横向格子， n是竖向格子
 *
 * 2. 初始状态 m >= 1 n >= 1
 * dp[1][1] = 2
 * dp[1][2] = 3
 * dp[2][1] = 3
 *
 * 3. dp 递推（状态流向）
 * 只能往右和往下
 * 多一个格子，上一个状态要么是在上边，要么是在左边
 *
 * dp[m][n] = dp[m-1][n] + dp[m][n-1]
 *
 * 4. dp 遍历顺序
 * 状态流向是正向的，从前往后推
 *
 * 5. 打印dp数组
 * dp[1][1] = 2
 * dp[2][2] = dp[1][2] + dp[2][1] = 3 + 3 = 6
 */

rl.on("line", (line) => {
    const input = line.split(" ");
    const m = parseInt(input[0]),
        n = parseInt(input[1]);

    const res = dpResolve(m, n);
    console.log(res);
});

function recursionResolve(m, n) {
    if(m <= 0 || n <= 0) {
        return 1;
    }
    return recursionResolve(m-1, n) + recursionResolve(m, n-1);
}

function dpResolve(m, n) {
    const dp = new Array(m+1).fill(1).map(() => new Array(n+1).fill(1));

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

  return dp[m][n];
}

唯一要注意的是生成的数组和题目给的m、n之间的差别，数组下标是从0开始的，这里为了简便和题意保持一致，生成了(m+1,n+1)的二维数组。