paizaラーニング レベルアップ問題集 DPメニュー JavaScript 【階段の上り方】階段の上り方 3

【階段の上り方】階段の上り方 3 (paizaランク B 相当)

解答例

dp[i]はi段目に上る方法の通りを表します。
dp[0] = 1;は、0段目にいる、という意味です。dp[0] = 0;だと、0段目にいないことになります。0段目にいるという意味で１です。0段目に至る方法も1つだけとして、1です。2だと、0段目に至る方法が２つあるという意味で、よくわからないことになります。

for (let i = 1; i <= n; i++)で一段ずつ見ていきます。

dp[i] = 0;は、i段目に至る方法がない、そこには行けないという意味の0が初期値です。

もしi>=aならば、i-a段目からi段目にいけるので、
dp[i]+=dp[i-a](またはdp[i] = dp[i] + dp[i - a];)です。
dp[i-a]>=1なら、i-a段目とi段目がつながるイメージです。
dp[i-a]=0なら、i-a段目にはいないので、つながりません。

b,cについても同様です。

すると、dp[i]に上るのに、何通りあるか、いくつ繋がるか、求まります。

これをi=nまで繰り返すと、0段目からn段目までの行き方が全てつながり、全部で何通りあるか求まります。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const [n, a, b, c] = lines[0].split(" ").map(Number);

const dp = Array(n + 1).fill(0);

dp[0] = 1;
for (let i = 1; i <= n; i++) {
  dp[i] = 0;
  if (i >= a) {
    dp[i] = dp[i] + dp[i - a];
  }
  if (i >= b) {
    dp[i] = dp[i] + dp[i - b];
  }
  if (i >= c) {
    dp[i] = dp[i] + dp[i - c];
  }
}
console.log(dp[n]);