0Pricing
Competitive Programming Academy · レッスン

階段登りとコインの組み合わせ

基本から 1 次元の典型的な漸化式を学びます

「階段登りとコインの組み合わせ」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

階段問題を知る

一度に1段または2段上れます。階段n段目まで到達する方法は何通りでしょうか。この典型的な1次元DPは、見方を変えたフィボナッチ数列にすぎません。

漸化式を見つける

i段目に立つには、i-1段目またはi-2段目から来ます。したがって、最後の2通りの移動を合計するdp[i] = dp[i-1] + dp[i-2]となります。

dp[i] = dp[i-1] + dp[i-2]

ベースケースを設定する

地面にとどまる方法は1通りで、1段目に到達する方法も1通りです。これらのベースケースが、表全体の初期値になります。

dp[0], dp[1] = 1, 1

表を埋めて答えを読む

上向きにループすると、最後のセルに通り数が入ります。解全体は小さなテーブルDPのループで求められます。

for i in range(2, n+1):
    dp[i] = dp[i-1] + dp[i-2]

2つの変数に縮約する

必要なのは直前の2つの値だけなので、配列をなくせます。このO(1)空間の実装は、競技プログラミングでよく使われます。

a, b = 1, 1
for _ in range(n):
    a, b = b, a+b

コインの組合せに切り替える

コインの額面が与えられたとき、金額Aを作る方法の数を数えます。ここでは順序を考慮しないため、列ではなく組合せを数えます。

coins = [1, 2, 5]

組合せの表

dp[x]を、xを作る方法の数とします。まず、0を作る方法として、コインの空集合による1通りを設定します。

dp = [0]*(A+1)
dp[0] = 1

コインのループを外側にする

コインのループを外側に、金額のループを内側に置きます。この順序なら、各組合せを順列としてではなく、ちょうど1回だけ数えられます。

for c in coins:
    for x in range(c, A+1):
        dp[x] += dp[x-c]

組合せと順列

ループの順序を入れ替えると、今度は順序付きの方法を数えます。ループの入れ子の順番だけで、答えの意味が変わります。

コイン交換の最小枚数版

最小枚数を求める場合は、合計ではなく最小値を保存します。無限大で初期化し、部分問題の最適値に1を加えます。

dp[x] = min(dp[x], dp[x-c] + 1)

1つのパターンが持つさまざまな形

階段問題とコイン問題には共通する形があります。各状態が、いくつかの直前の状態の合計または最小値を取るのです。これに気づけば、コードは自然に書けます。

確認問題

コインの組合せを数えるとき、重複を避けるループ順序はどれでしょうか。

まとめ：最後の移動を合計する

これで階段問題とコインの通り数を1次元の漸化式で解けるようになりました。各答えは複数の過去の状態を合計したもので、ループ順序によって組合せと順列が決まります。

よくある質問

「階段登りとコインの組み合わせ」レッスンは無料ですか？

はい。「階段登りとコインの組み合わせ」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「階段登りとコインの組み合わせ」で何を学びますか？

基本から 1 次元の典型的な漸化式を学びます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「階段登りとコインの組み合わせ」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. メモ化と tabulation の比較
  2. 状態と遷移を定義する
  3. 階段登りとコインの組み合わせ
  4. 最長増加部分列
← Competitive Programming Academyに戻る