毎日のアルゴリズム: 階段登り問題

[[433205]]

階段を登っているとします。建物の最上部に到達するまでに n 歩かかります。

一度に1段または2段登ることができます。建物の最上階まで登るには、何通りの方法がありますか?

注: n は正の整数です。

例1:

入力: 2
出力: 2
説明: 建物の最上階に到達するには 2 つの方法があります。
 1. 1次 + 1次
2. 2次

例2:

入力: 3
出力: 3
説明: 屋根に登るには 3 つの方法があります。
 1. 1次 + 1次 + 1次
2. 1次 + 2次
3. 2次 + 1次

解決策: 動的プログラミング

動的プログラミング (DP) は、複雑な問題を小さな問題に分割して解決する戦略です。ただし、各サブ問題が互いに独立していることを要求する分割統治アルゴリズムとは異なり、動的プログラミングのサブ問題は相互に関連しています。

分割統治法は、その名の通り、分割して統治することです。複雑な問題を 2 つ以上の類似したサブ問題に分割し、そのサブ問題をさらに小さなサブ問題に分割して、簡単に解決できるまで続けます。サブ問題が解決されると、元の問題の解決策はサブ問題の解決策の組み合わせになります。

動的プログラミングを使用して問題を解決する場合、いくつかの重要な手順に従う必要があります。

• サブ問題の定義
• 繰り返し解決する必要があるサブ問題の一部を実装する
• 境界条件を特定して解決する

ステップ1: サブ問題を定義する

dp[n]を使用してn番目のステップのオプションの数を表し、質問から最後のステップが2ステップまたは1ステップになる可能性があることがわかっている場合、n番目のステップのオプションの数は、n-1番目のステップのオプションの数とn-2番目のステップのオプションの数の合計に等しくなります。

ステップ2: 繰り返し解決する必要があるサブ問題を実装する

dp[n] = dp[n−1] + dp[n−2]

ステップ3: 境界条件を特定して解決する

// レベル 0、最初のオプション
dp[0]=1
 // レベル 1 も 1 つのソリューションです
dp[1]=1

最後のステップ: 末尾のコードをコードに変換し、いくつかのエッジケースを処理する

階段を登る =関数(n) {
    dp = [1, 1]とする
( i = 2; i <= n; i++ とします) {
        dp[i] = dp[i - 1] + dp[i - 2]
    }
 dp[n]を返す
}

複雑性分析:

• 時間計算量: O(n)
• 空間計算量: O(n)

空間の複雑さを最適化:

階段を登る =関数(n) {
    res = 1、n1 = 1、n2 = 1とします。
 ( i = 2; i <= n; i++ とします) {
        レス = n1 + n2
        1 = 2 です
        n2 = レス
    }
戻り値
}

空間計算量: O(1)

リートコード: https://leetcode-cn.com/problems/climbing-stairs/solution/pa-lou-ti-wen-ti-by-user7746o/