階段を登るための最小コストを使用するデータ構造とアルゴリズム

[[443068]]

最小限のコストで階段を登る

LeetCode の問題へのリンク: https://leetcode-cn.com/problems/min-cost-climbing-stairs

配列の各添字はステップとして機能し、i番目のステップは負でないスタミナコスト値cost[i]に対応します（添字は0から始まります）。

階段を登るたびに、対応するスタミナを消費する必要があります。対応するスタミナを支払うと、1 段登るか 2 段登るかを選択できます。

最上階まで到達するための最小コストを見つけてください。最初は、最初のステップとしてインデックス 0 または 1 の要素から開始することを選択できます。

例1:

• 入力: コスト = [10, 15, 20]
• 出力: 15
• 説明: 最もコストが低いのは、コスト[1]から始めて、はしごの一番上まで2ステップ進むことです。合計コストは15です。

例2:

• 入力: コスト = [1, 100, 1, 1, 100, 1, 1, 100, 1]
• 出力: 6
• 説明: 最も安価な方法は、コスト[0]から始めて、1を1つずつ調べ、コスト[3]をスキップして、合計6を費やすことです。

ヒント：

• コストの長さは[2, 1000]の範囲です。
• cost[i]は[0, 999]の範囲の整数値になります。

アイデア

この質問は、昨日の動的計画法、つまり階段を登るという問題のコスト版と言えます。

質問の説明に注意してください: 階段を登るたびに、対応する体力を消費する必要があります。対応する体力を支払ったら、1 段登るか 2 段登るかを選択できます。

したがって、例 1 では、ラダーの一番上に到達するために 15 を 1 回消費するだけで済み、最後のステップはコストがかからないと理解できます。

質問を読んだ後、動的プログラミングが必要であり、貪欲は不可能であることを誰もが理解するはずです。

dp配列と添え字の意味を決定する

動的プログラミングを使用する場合、ステータスを記録するための配列が必要です。この問題では、1次元配列dp[i]のみが必要です。

dp[i]の定義: i番目のステップに到達するために必要な最小エネルギー量はdp[i]です。 （最初のステップは費やす必要があると考えられることに注意してください）

dp 配列の定義については、誰もが明確に理解する必要があります。

再帰式を決定する

dp[i]を取得する方法は2つあります。1つはdp[i-1]で、もう1つはdp[i-2]です。

では、dp[i-1]とdp[i-2]のどちらを選択すべきでしょうか?

最小のものを選択する必要があるため、dp[i] = min(dp[i - 1], dp[i - 2]) + cost[i]となります。

ここでcost[i]がcost[i-1]、cost[i-2]などではなく追加されている理由に注目してください。質問では、階段を登るたびに、対応する量の体力を消費する必要があると言っているからです。

dp配列を初期化する方法

dp 配列の定義によれば、i 番目のステップに費やされる最小限の物理的な労力に dp 配列を初期化することは不可能であるため、実際には dp 配列を初期化することは困難です。

次に、再帰式を見てみましょう。dp[i]はdp[i-1]とdp[i-2]から派生します。すべてのdp[i]を初期化することは不可能なので、dp[0]とdp[1]のみを初期化すれば十分です。その他は最終的にdp[0]dp[1]から派生します。

初期化コードは次のようになります。

ベクトル< int > dp(cost.size ( ));
 dp[0] = コスト[0];
 dp[1] = コスト[1];

トラバース順序を決定する

最後のステップは、再帰式と初期化を行うことです。どのように走査するのでしょうか?

この問題のトラバース順序は実際には非常に単純で、非常に単純なため、多くの学生がこのステップを無視してコードを直接記述します。

これは階段をシミュレートしており、dp[i]はdp[i-1]dp[i-2]から派生しているため、コスト配列を前から後ろへ走査するだけで済みます。

しかし、少し難しい動的プログラミングの場合、走査順序を決定するのは簡単ではありません。

たとえば、01 バックパックの場合、2 つの for ループがあることは誰もが知っています。1 つはアイテムをトラバースする for ループで、もう 1 つはバックパックの容量をトラバースする for ループです。では、バックパックの容量をトラバースする for ループとアイテムをトラバースする for ループをそれぞれ 1 つずつ使用しないのはなぜでしょうか。また、1 次元の dp 配列を使用する場合、バックパックの容量を逆の順序でトラバースする必要があるのはなぜでしょうか。

これらはすべて、トラバーサル順序と密接に関連しています。もちろん、ナップサック問題に関しては、後続の「Code Random Thoughts」で詳しく説明します！

dp配列を導出する例

例 2: cost = [1, 100, 1, 1, 100, 1, 1, 100, 1] として、dp 配列の状態変化を次のようにシミュレートします。

最小限のコストで階段を登る

コードに問題がある場合は、dp 配列を出力して、上記で導出された配列と同じかどうかを確認してください。

上記の分析後、全体的な C++ コードは次のようになります。

 // バージョン 1
クラスソリューション{
公共：
 int minCostClimbingStairs(ベクトル< int >& コスト) {
        ベクトル< int > dp(cost.size ( ));
        dp[0] = コスト[0];
        dp[1] = コスト[1];
 ( int i = 2; i < cost.size ( ); i++) {
            dp[i] = min (dp[i - 1], dp[i - 2]) + コスト[i];
        }
        // 最後のステップはコストがかからないと理解できるので、最初のステップと2番目のステップの最小値を取ることに注意してください
戻る 最小(dp[コスト.サイズ( ) - 1]、dp[コスト.サイズ( ) - 2]);
    }
 };

• 時間の計算量:
• 空間の複雑さ:

dp[i] は最初の 2 桁から導出されるため、空間計算量も最適化され、dp 配列は不要になります。C++ コードは次のとおりです。

 // バージョン 2
クラスソリューション{
公共：
 int minCostClimbingStairs(ベクトル< int >& コスト) {
コスト0をdp0に変換する。
コスト[1]を整数dp1で割る。
 ( int i = 2; i < cost.size ( ); i++) {
 int dpi = min (dp0, dp1) + コスト[i];
            dp0 = dp1; // 最初の2桁を記録する
            dp1 = 解像度;
        }
戻る 最小（dp0、dp1）;
    }
 };

• 時間の計算量:
• 空間の複雑さ:

もちろん、このように書くことはお勧めしません。直感的で簡潔なバージョン 1 を書くだけで十分です。

以降の説明ではバージョン2の書き方は無視する場合もあります。このような書き方があることを皆さんに知っていただければ十分です。

拡大する

この質問の説明は確かに少し魔法のようです。

タイトルの説明: 階段を登るたびに、対応する体力を消費する必要があります。対応する体力を支払ったら、1 段登るか 2 段登るかを選択できます。

例1:

入力: コスト = [10, 15, 20] 出力: 15

質問の説明から、最初のステップでは物理的な努力が必要ないか、最後のステップでは物理的な努力が必要ないかのどちらかであることがわかります。私の個人的な理解では、この質問は実際には最初のステップでは支払いが必要であることを意味しています。階段を登るときには、その分だけ体力を使わないといけないからです！

したがって、私が定義したdp[i]は、最初のステップでは物理的な労力が必要であり、最後のステップでは既に支払われているため物理的な労力は必要ないことを意味しています。

もちろん、dp[i]を次のように定義することもできます。最初のステップでは物理的なエネルギーは消費されず、最後のステップでは物理的なエネルギーが消費されます。

したがって、コードは次のように記述されます。

クラスソリューション{
公共：
 int minCostClimbingStairs(ベクトル< int >& コスト) {
        ベクトル< int > dp(cost.size ( ) + 1);
        dp[0] = 0; // デフォルトでは、最初のステップでは体力は消費されません
        1 = 0;
 ( int i = 2; i <= cost.size ( ); i++) {
            dp[i] =最小(dp[i - 1] + コスト[i - 1]、dp[i - 2] + コスト[i - 2]);
        }
 dp[cost.size ( )]を返します。
    }
 };

これはよりスムーズな書き方のように思えますが、トピックの説明と一致していないようです。ハハハ、質問の意味についてそんなに細かく考える必要はありません。あなたが知っておく必要があるのは、最初のステップでお金を使わないか、最後のステップでお金を使わないかのどちらかだけです。すべて大丈夫です。

要約する

この問題は、昨日の動的プログラミング（階段を登る）よりも少し難しいですが、全体的な考え方は同じです。

動的プログラミング：フィボナッチ数列から動的プログラミング：階段登りへ、そして今日の質問ですが、段階的な進歩を感じましたか？

各シリーズの初めに、録画した友人の何人かは、質問が簡単すぎると言って、すぐに難易度を上げるように頼みました。しかし、録画した友人の中には、質問が少し難しくて、ほとんどついていけないと言う人もいました。

実際、私が選んだ問題はすべて目的を持っていました。たとえ簡単な問題であっても、方法論を練習するためのものでした。難易度は徐々に、次々と上がっていきました。

しかし、難しい質問をランダムに選んで話すこともできます。これは実は一番簡単な方法です。質問の順番を気にする必要はありません。自分の気分に合った質問を選んで話すだけです。

難しいのは、質問をグラデーションで並べ、段階的に進め、統一された方法論に従ってすべてをつなぎ合わせることです。笑。だから、急がせず、私のペースに段階的に付いてきてください。

アルゴリズムを学ぶには、「Code Thoughts」を探してください。問題ありません!

その他の言語

ジャワ

クラスソリューション{
公共  int階段登りの最小コスト( int [] コスト) {
        コスト == null || コスト.長さ == 0 の場合 {
 0を返します。
        }
        コスト.長さ == 1 の場合
返品費用[0];
        }
 int [] dp = 新しいint [cost.length];
        dp[0] = コスト[0];
        dp[1] = コスト[1];
 ( int i = 2; i < cost.length; i++) {
            dp[i] = Math.min (dp[i - 1], dp[i - 2]) + コスト[i];
        }
        //最後のステップ、最後から2番目のステップを登れば、最後のステップの物理的な努力は無視できます
Math.min ( dp [cost.length - 1], dp[cost.length - 2] )を返します。
    }
 }

パイソン

クラスソリューション:
    def minCostClimbingStairs(self, cost: List[ int ]) -> int :
        dp = [0] * (len(コスト))
        dp[0] = コスト[0]
        dp[1] = コスト[1]
 iが範囲(2, len(コスト))内にある場合:
            dp[i] =最小(dp[i - 1], dp[i - 2]) + コスト[i]
戻る 最小(dp[len(コスト) - 1]、dp[len(コスト) - 2])

行く

func minCostClimbingStairs(cost [] int ) int {
 dp := make([] int , len(コスト))
 dp[0]、dp[1] = コスト[0]、コスト[1]
 i := 2; i < len(コスト); i++ {
  dp[i] =最小(dp[i-1], dp[i-2]) + コスト[i]
 }
戻る 最小(dp[len(コスト)-1], dp[len(コスト)-2])
 } 
 
関数min (a, b int ) int {
 もしa < b {
返す​
 }
 bを返す
}

ジャバスクリプト

var minCostClimbingStairs = function (cost) {
    定数dp = [ コスト[0], コスト[1] ] 
 
 ( i = 2; i < cost.length; ++i とします) {
        dp[i] = Math.min (dp[i -1] + コスト[i]、dp[i - 2] + コスト[i])
    } 
 
 Math.min (dp[cost.length - 1], dp[cost.length - 2])を返す
};