動的計画法で通行料つきの階段をいちばん安く上る

段ごとに決まった通行料を払うと、そこから 1 段か 2 段上れる階段で、いちばん上へ抜けるまでの合計を最も安くします。前の 2 段の答えだけを持ち歩く、階段の数え方の続きの練習です。

海外で定番の問題リスト 4 本には入っていません

問題

階段の段ごとに通行料が決まっていて、並び cost で受け取ります。cost[i] は i 段目の料金です。i 段目で料金を払うと、そこから 1 段か 2 段上へ進めます。いちばん上 (最後の段のさらに 1 つ上) へ抜けるまでに払う合計の、最も安い値を返す関数を書いてください。

始めは 0 段目か 1 段目のどちらかに、料金を払わずに立てます
料金は、その段から進むときに払います。立っただけでは払いません
cost の長さは 2 以上 1000 以下で、どの料金も 0 以上 999 以下の整数です

入力と出力の例

例 1

0 段目から始めて 3 を払い 2 段目へ、2 を払い 4 段目へ、1 を払って上へ抜けます。合計は 6 です。1 段目から始めると 8 を払うことになり、高くつきます。

cost = [3, 8, 2, 9, 1]

例 2

1 段目から始め、料金 1 の段だけを踏んで 2 段ずつ上ります。

cost = [5, 1, 5, 1, 5, 1]

例 3

2 段しかないときは、1 段目から 4 を払えば 1 回で上へ抜けられます。

cost = [7, 4]

面接での聞かれ方

面接では、階段の上り方を数える問題のすぐ後に、決まりを 1 つ足した形で出されます。

「段ごとに料金があります。いちばん上まで最も安く上ると、いくらですか」
最初に「ゴールは最後の段ですか、その 1 つ上ですか？」「始めの段の料金は払いますか？」と確かめられるかを見られます
書き終えると「表を使わずに、記憶を O(1) にできますか？」と続きます

ゴールの位置と、料金を払う時を取り違えると答えがずれます。手で数える前に決まりを口に出して確かめます。

ヒント

まだ開いていません

付箋は 4 枚。下の段ほど答えに近づきます

ヒント 2
ヒント 3
ヒント 4答えに近い

アルゴリズムのチートシートの「動的計画法 (DP)」に、この型の要点を表とコードでまとめています。

動的計画法は、途中の答えを覚えておいて、同じ計算をやり直さない書き方です。漸化式で言い直せる問題が多いです。

数学1-2 シグマと漸化式
CS2-9 動的計画法

まず考える手順

段 1

全部の上り方を試すと、1 段か 2 段かを毎回選ぶので、上り方の数は段の数に対して指数的に増えます。1000 段では終わりません。

段 2

「i 段目に立つまでに払った最も安い合計」を best[i] と置きます。i 段目へ来る直前は、i - 1 段目で料金を払って 1 段上ったか、i - 2 段目で払って 2 段上ったかのどちらかです。なので best[i] は best[i-1] + cost[i-1] と best[i-2] + cost[i-2] の安いほうです。

段 3

始めは 0 段目と 1 段目に無料で立てるので、best[0] と best[1] は 0 です。ゴールは最後の段の 1 つ上なので、答えは best[n] (n は段の数) です。

段 4

best[i] を求めるのに使うのは、すぐ前の 2 つだけです。表を持たず、2 つの変数を持ち歩けば足ります。

解答

Python

def stair_cost(cost):
    two, one = 0, 0
    n = len(cost)
    for i in range(2, n + 1):
        a = one + cost[i - 1]
        b = two + cost[i - 2]
        two = one
        one = min(a, b)
    return one

JavaScript

function stairCost(cost) {
  let two = 0;
  let one = 0;
  const n = cost.length;
  for (let i = 2; i <= n; i++) {
    const a = one + cost[i - 1];
    const b = two + cost[i - 2];
    two = one;
    one = Math.min(a, b);
  }
  return one;
}

Go

func stairCost(cost []int) int {
	two, one := 0, 0
	n := len(cost)
	for i := 2; i <= n; i++ {
		a := one + cost[i-1]
		b := two + cost[i-2]
		two = one
		one = min(a, b)
	}
	return one
}

one と two は、段 2 の best[i-1] と best[i-2] です。a は 1 つ下の段から 1 段上る場合、b は 2 つ下の段から 2 段上る場合の合計です。ループの終わりで 1 つずつ前へずらします。ループを抜けたときの one が best[n] で、いちばん上へ抜けたときの合計です。

計算量

時間は O(n) です (n は段の数)。どの段も 1 回ずつ見ます
使う記憶は O(1) です。持つのは 2 つの変数だけです
best の表を全部持つ書き方も時間は同じで、記憶が O(n) になります

よくある間違い

最後の段をゴールにする。答えを best[n-1] にすると、最後の段の料金を払わずに済ませたことになります。例 3 で 0 を返したら、この間違いです
始めの段の料金を先に払う。 best[0] = cost[0] と置くと、立っただけで払ったことになり、料金を 2 回数える道ができます
安い段を欲張りで選ぶ。始めに安いほうの段に立ち、次の 2 段のうち安いほうへ進む決め方は外れます。cost = [1, 2, 9, 1, 100] では、0 段目から 1、2、1 と払って 4 になります。1 段目から始めて 2 と 1 を払う 3 が答えです

解答を動かした版 Python 3.14.7Node.js 24.22.1Go 1.24.2確認日 2026年11月8日

main.py

def stair_cost(cost: list[int]) -> int:
    """
    Goal: 何を返すか

    idea1: まず思いつく案
    -> runtime: O(?)  space: O(?)

    idea2: もっと速い案
    -> runtime: O(?)  space: O(?)

    edge case: 空、1 つだけ、など
    """
    # ここに書きます
    pass


# 「実行」を押すと、この行の結果が出ます
print(stair_cost([3, 8, 2, 9, 1]))

できているか「例で確かめる」を押すと、問題の例を全部この関数に渡して、通ったかをここに出します