【DPメニュー】階段の上り方 2 (paizaランク B)-解答例-PHP編

2022年8月13日

【DPメニュー】> 【階段の上り方】STEP: 2 階段の上り方 2 (paizaランク B 相当) [難易度: 1742 ±17]

※リンク先へ移動するためには[paiza]へのログインが必要です。

問題文

整数 n, a, b が与えられます。
階段を上るのに、1歩で a 段または b 段を上ることができるとき、n 段の階段を上る方法は何通りあるでしょうか。

(ヒント)

前問とやることは同じです。ただ、n, a, b の値によっては答えが0になることがあるので注意しましょう。例えば、n = 4, a = 3, b = 5 のとき、答えは0です。(1歩で3段か5段上ることができるとき、ちょうど4段の階段を上る方法は存在しない)

入力値（例）
11 3 4

出力値（例）
3

解答例

<?php
    list($n, $a, $b) = explode(" ", trim(fgets(STDIN)));
    
    $dp[0] = 1;
    
    for ($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];
        }
    }
    
    echo $dp[$n];
?>

<?php

list($n, $a, $b) = explode(" ", trim(fgets(STDIN)));

$dp[0] = 1;

for ($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];

}

echo $dp[$n];

(ヒント)

解答例

カテゴリー