貪欲で最後のマスまでの最少の跳ぶ回数を求める

すごろくのマスごとに進める歩数の上限が決まっているとき、最後のマスに着くまでの跳ぶ回数の最少を返す。「あと 1 回跳べば届く範囲」を段ごとに広げていけば、前から 1 回なめるだけで数えられます。

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

問題

すごろくのマスが一列に並び、マス i からは 1 歩以上 steps[i] 歩以下の好きな歩数だけ前へ進めます。最初のマス (番号 0) から始めて、最後のマス (番号 len(steps) - 1) に着くまでの、跳ぶ回数の最少を返す関数を書いてください。

どの入力でも、最後のマスには必ず着けます
後ろへ戻ることはできません
マスが 1 つだけなら、最初から着いているので答えは 0 です
steps の長さは 1 以上 100000 以下、値はどれも 0 以上 1000 以下です

入力と出力の例

例 1

マス 0 から 1 歩でマス 1 へ、4 歩でマス 5 へ、2 歩でマス 7 へ跳ぶ 3 回が最少です。マス 0 から 2 歩でマス 2 へ跳ぶと、そこからはマス 5 に届きません。

steps = [2, 4, 1, 1, 0, 3, 1, 2]

例 2

マスが 1 つだけなので、跳ぶ必要はありません。

steps = [0]

例 3

マス 0 から 5 歩で、1 回で最後のマスに着けます。

steps = [5, 1, 1, 1, 1, 1]

面接での聞かれ方

面接では、「最後まで行けるか」を判定する問題の続きとして出されることが多いです。

「必ず最後まで行けるとして、最少で何回跳べばよいですか」
最初に動的計画法や幅優先探索で書き、「記憶を O(1) にできますか」と聞かれて貪欲に直す流れもあります
「着けない入力が来たらどうしますか」と、前提を聞かれることもあります

必ず着けるという前提があるかを、書く前に確かめておきます。前提が無いなら、着けないときに何を返すかを決めます。

ヒント

まだ開いていません

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

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

アルゴリズムのチートシートの「配列と文字列」に、この型の要点を表とコードでまとめています。

配列と文字列の問題は、全部の組を調べると手間が大きくなる所を、窓や左右の添字で減らす形が多いです。

まず考える手順

段 1

素直に考えると、マスごとに「そこまでの最少の回数」を持ち、前のマスから届く先の値を小さい方へ直していくことになります。マスごとに最大 steps[i] 個の先を直すので、最悪 O(n × 最大の歩数) かかります。

段 2

幅優先探索の目で見ると、0 回で着けるのはマス 0 だけ、1 回で着けるのはマス 1 から steps[0] まで、というように、k 回で着けるマスはいつもひと続きの範囲になります。k + 1 回で着ける範囲の右端は、k 回の範囲の中のマスから届く最も遠いマスです。

段 3

いまの回数で着ける範囲の右端 end と、次の 1 回で届く最も遠いマス far を持ち、マスを前から見ます。マスごとに far を広げ、見ているマスが end に来たら、範囲を使い切ったので回数を 1 足し、end を far にします。最後のマスに着いた後は跳ばないので、見るのは最後のマスの手前までです。

解答

Python

def min_jumps(steps):
    jumps = 0
    end = 0
    far = 0
    for i in range(len(steps) - 1):
        far = max(far, i + steps[i])
        if i == end:
            jumps += 1
            end = far
    return jumps

JavaScript

function minJumps(steps) {
  let jumps = 0;
  let end = 0;
  let far = 0;
  const n = steps.length;
  for (let i = 0; i < n - 1; i++) {
    far = Math.max(
      far, i + steps[i],
    );
    if (i === end) {
      jumps++;
      end = far;
    }
  }
  return jumps;
}

Go

func minJumps(steps []int) int {
	jumps, end, far := 0, 0, 0
	n := len(steps)
	for i := 0; i < n-1; i++ {
		far = max(far, i+steps[i])
		if i == end {
			jumps++
			end = far
		}
	}
	return jumps
}

end が最後のマス以上になった後も、ループは手前まで回りますが、i が end に追いつかないので回数は増えません。

計算量

時間は O(n) です。マスを前から 1 回なめ、1 マスごとの手間は一定です
使う記憶は O(1) です。持つのは回数と end と far だけです
幅優先探索で待ち行列を使う書き方でも答えは同じですが、記憶が O(n) 要ります

よくある間違い

最後のマスまでループを回す。 range(len(steps)) と書くと、最後のマスに着いた所で i == end になったとき、要らない 1 回を足すことがあります。例 2 の [0] では 1 を返してしまいます
いつも最大の歩数で跳ぶ。例 1 でマス 0 から最大の 2 歩でマス 2 へ跳ぶと、そこから届くのはマス 3 までで、遠回りになります。1 本の道を選ぶのではなく、範囲で考えます
跳ぶたびに最も遠いマスへ移ったと考えて、次のマスを far から始める。 範囲の中の手前のマスから、もっと遠くへ届くことがあります。範囲の中のマスは全部見て far を広げます
far を広げる前に回数を足す。 i == end の確かめを far の更新より先にすると、マス end 自身から届く先が end に入りません。例 1 では最初の回で end が 0 のまま残り、そのあと広がらないので 1 を返します

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

main.py

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

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

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

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


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

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