题解 | #走方格的方案数#
走方格的方案数
https://www.nowcoder.com/practice/e2a22f0305eb4f2f9846e7d644dba09b
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void (async function () {
// Write your code here
while ((line = await readline())) {
let [n, m] = line.split(" ").map((v) => parseInt(v));
let dp = [];
for (let i = 0; i <= n; i++) {
dp[i] = [];
for (let j = 0; j <= m; j++) {
if (i === 0 || j === 0) {
dp[i][j] = 1;
}
}
}
for (let i = 1; i <= n; i++) {
for (let j = 1; j <= m; j++) {
// 状态转移
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
console.log(dp[n][m]);
}
})();
n × m的方格沿边线走，和（n+1) × (m+1)的方格沿方格走到最后一格是相同的方案，故可以理解为走（n+1) × (m+1)方格。进入左上角第一个方格只有一种方案，故dp[0][0]=1，除此之外，进入第一行的方格和第一列的方格都只有一种走法：第一行只能从左边的那个方格走过来，第一列的方格只能由上面的方格走下来，其余方格可由左侧或上方进入，所以
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
最后一格dp[n][m]即为总的方案数。
