DPメニュー【階段の上り方 1 〜 3】
【階段の上り方 1】コード
reader.on('close', () => {
const n = Number(lines[0]); // 3
const dp = [1]; // 0 段目まで上がる方法は 1通り(移動しない)
for (let i = 1; i <= n; i++) { // ループ範囲は 1 段 ~ n 段
dp[i] = 0; // i 段目まで上がるパターン数を 0 で初期化
if (i >= 1) {
dp[i] = dp[i] + dp[i - 1]; // i - 1 段目から 1 段上がるパターン
}
if (i >= 2) {
dp[i] = dp[i] + dp[i - 2]; // i - 2 段目 から ２段 上がるパターン
}
}
console.log(dp[n]);
});
n===3 の場合dp の値は [1, 1, 2, 3 ] でした。i - 1 段目から 1 段上るパターンと i - 2 段目から 2 段上るパターンがあるので １ 段 ずつ進めながら dp[i] にdp[[i - 1]とdp[[i - 2]を加算しています。
【階段の上り方 2】コード
reader.on('close', () => {
const [n, a, b] = lines[0].split(' ').map(Number);
const dp = [1]; // 0 段目まで上がる方法は 1通り(移動しない)
for (let i = 1; i <= n; i++) { // ループ範囲は 1 段 ~ n 段
dp[i] = 0;
if (i >= a) {
dp[i] = dp[i] + dp[i - a]; // i - a 段目から a 段上がるパターン
}
if (i >= b) {
dp[i] = dp[i] + dp[i - b]; // i - b 段目から b 段上がるパターン
}
}
console.log(dp[n]);
});階段を上がるパターンを標準入力から受け取っています。
【階段の上り方 3】コード
reader.on('close', () => {
const [n, a, b, c] = lines[0].split(' ').map(Number);
const dp = [1]; // 0 段目まで上がる方法は 1通り(移動しない)
for (let i = 1; i <= n; i++) { // ループ範囲は 1 段 ~ n 段
dp[i] = 0;
if (i >= a) {
dp[i] = dp[i] + dp[i - a]; // i - a 段目から a 段上がるパターン
}
if (i >= b) {
dp[i] = dp[i] + dp[i - b]; // i - b 段目から b 段上がるパターン
}
if (i >= c) {
dp[i] = dp[i] + dp[i - c]; // i - c 段目から c 段上がるパターン
}
}
console.log(dp[n]);
});階段を上がるパターンが 3 通りになりました。
コメント