第107回【JavaScript】階段の上り方 1、階段の上り方 2

2024年2月14日

現在取り組んでいるのは、paiza ラーニング問題集「DPメニュー」になります。

環境構築不要！初心者でも楽しく入門できるプログラミング学習サイト【paizaラーニン

プログラミング学習サイト【paizaラーニング】のメインページ。paiza独自のシステムにより、面倒な環境 ...

 https://paiza.jp/works

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

JavaScript をゼロから勉強してみよう、のコーナー 107 回目です。

とあるメーカーさんに問合せをしたのですが、その返信がありません。回答に時間がかかるのならば、せめて一次返信、問合せを受け取ったよ、くらいは教えてほしいものです。もう 1 回問合せをし直すべきか、もうしばらく待つべきか、とても悩んでいます。（3 日経過）

それでは、今日も頑張ってみようと思います。

階段の上り方 1 (paizaランク B 相当)

階段の上り方 1 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング

問題を解いてスキルアップ！みんなも一緒に解いてみよう！

 https://paiza.jp/works/mondai/dp_primer/dp_primer_stairs_ste...

dp[0] <- 1

for i = 1 to n
    dp[i] <- 0
    if i >= 1 then
        dp[i] <- dp[i] + dp[i-1]    // i-1 段目から1段上って i 段へ到達
    if i >= 2 then
        dp[i] <- dp[i] + dp[i-2]    // i-2 段目から2段上って i 段へ到達

print dp[n]

n

3

3

DP 問題の本丸に乗り込んできた感じ。理解出来ると、とても面白い。

JavaScript

process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
  const n = Number(lines[0]);
  const dp = Array(n+1);
  dp.fill(1);
  for (let i = 1; i <= n; i++) {
      dp[i] = 0;
      if (i >= 1) dp[i] += dp[i-1];
      if (i >= 2) dp[i] += dp[i-2];
  }
  console.log(dp[n]);
});

Python

n = int(input())
dp = [1] * (n+1)
for i in range(1,n+1):
    dp[i] = 0
    if i >= 1:
        dp[i] = dp[i] + dp[i-1]
    if i >= 2:
        dp[i] = dp[i] + dp[i-2]
print(dp[n])

階段の上り方 2 (paizaランク B 相当)

階段の上り方 2 | レベルアップ問題集 | プログラミング学習サイト【paizaラーニング

問題を解いてスキルアップ！みんなも一緒に解いてみよう！

 https://paiza.jp/works/mondai/dp_primer/dp_primer_stairs_ste...

n a b

11 3 4

3

さっきの問題の応用。しかし、a と b の値によっては、到達するパターンがない可能性、解答が 0 になる可能性があることに注意しなければならない。

JavaScript

process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
  const [n,a,b] = lines[0].split(/\s/).map(Number);
  const dp = Array(n+1).fill(0);
  dp[0] = 1;
  for (let i = 1; i <= n; i++) {
      if (i >= a) dp[i] += dp[i-a];
      if (i >= b) dp[i] += dp[i-b];
  }
  console.log(dp[n]);
});

Python

n,a,b = map(int,input().split())
dp = [0] * (n+1)
dp[0] = 1
for i in range(1,n+1):
    if i >= a:
        dp[i] = dp[i] + dp[i-a]
    if i >= b:
        dp[i] = dp[i] + dp[i-b]
print(dp[n])

最後に

多分、ゆっくり整理して考えれば、やっていることは単純で、理解出来るのだと思います。しかし、それをコードとして書くのはまた別の問題。こういう解き方を知っていれば、幾らでも応用が利きます。

JavaScript において、配列の初期値を設定する方法として fill を利用していますが、速度的にどうなんでしょう。Python だと、None を初期値として配列を作ると早い、という話がありますが・・・。

引き続き、よろしくお願いいたします！

Python の第107回はこちら

第107回【Python】階段の上り方 1、階段の上り方 2

現在取り組んでいるのは、paiza ラーニング問題集「DP メニュー」になります。 paiza ラーニング はじ ...

 https://luna-leo.com/2023/08/03/post-2443/