これらは、データ構造とアルゴリズムにおける動的プログラミングのコツです。

[[442276]]

動的計画法理論の基礎

動的プログラミングとは何か

動的プログラミング (英語: Dynamic Programming) は DP とも呼ばれ、問題に重複するサブ問題が多数ある場合は、動的プログラミングを使用するのが最も効果的です。

したがって、動的プログラミングにおける各状態は、前の状態から導出されなければなりません。これは、状態を導出せず、ローカル状態から最適な状態を直接選択する貪欲プログラミングとは異なります。

「貪欲アルゴリズムについて、これだけは知っておいてください！」では、ナップサック問題の例を挙げました。

たとえば、N 個のアイテムがあり、最大重量 W を運ぶことができるバックパックがあるとします。 i番目の項目の重みはweight[i]であり、結果の値はvalue[i]です。各アイテムは 1 回しか使用できません。アイテムの合計価値を最大化するには、どのアイテムをバックパックに入れるべきかを調べます。

動的計画法では、dp[j]はdp[j-weight[i]]から導出され、max(dp[j], dp[j - weight[i]] + value[i])が取得されます。

しかし、欲張りな場合は、毎回最大または最小の項目を選択するだけになり、前の状態とは何の関係もありません。

したがって、貪欲法では動的計画法の問題を解決できません。

実際、動的ルールと貪欲さの理論的な違いに焦点を当てる必要はありません。後で質問を解くと自然に理解できるようになります。

さらに、動的プログラミングを説明する多くの記事では、最適なサブ構造や重複するサブ問題について説明しています。これらは教科書の定義であり、わかりにくく実用的ではありません。

ご存知のように、動作規則は前の状態から導出され、貪欲法では最適なものを局所的に直接選択するため、問題を解決するにはこれで十分です。

上記のナップサック問題については、後ほど詳しく説明します。

動的プログラミングの問題解決手順

動的制御問題を解くとき、多くの学生は誤解に陥ります。つまり、状態遷移式を暗記し、式に従って変更してからコードを書き始めればよいと考えます。問題を解いた後でも、dp[i]が何を表しているかがまだ明確ではありません。

ぼんやりした状態で、問題をパスします。少し難しい問題に遭遇すると、まったく解けなくなり、解答を見て、また書き写すという悪循環に陥ります。

状態遷移式（再帰式）は非常に重要ですが、動的制御は再帰式だけではありません。

動的プログラミングの問題については、次の 5 つのステップに分解します。この 5 つのステップを理解して初めて、動的プログラミングを本当にマスターしたと言えます。

1. dpテーブルと添え字の意味を決定する
2. 再帰式を決定する
3. dp配列を初期化する方法
4. トラバース順序を決定する
5. dp配列を導出する例

なぜ最初に再帰式を決定し、その後初期化を考慮する必要があるのか​​疑問に思う学生もいるかもしれません。

場合によっては、再帰式によって dp 配列の初期化方法が決まるからです。

以下の説明では、この5つのポイントに焦点を当てて説明します。

動的計画法の問題を練習したことがある生徒は、再帰式の重要性を理解しており、再帰式が決定されれば問題を解決できると感じるかもしれません。

実際、再帰式を決定することは、問題を解決するための 1 つのステップにすぎません。

生徒の中には、再帰式は知っていても、dp 配列の初期化方法や正しい走査順序を理解していない人もいます。その結果、式は書き留めても、プログラムを変更することはできません。

読み進めていくと、この 5 つのステップの重要性が徐々に感じられるようになるでしょう。

動的プログラミングをデバッグする方法

ほとんどの学生は、動的ルールに関する質問に答えるときにこれを行っていると思います。

解答を見て、理解できたと感じたら、それをコピーします。きちんと描くことができれば、すべてうまくいきます。失敗した場合は、どのように修正しても合格しません。dp 配列の初期化、再帰式、トラバース順序は、理解のブラックボックス状態です。

動的ルールの質問を書くとき、コードに問題が発生するのは普通のことです。

問題を見つける最良の方法は、dp 配列を印刷し、それが自分の考えに従って導出されているかどうかを確認することです。

生徒の中には、dp をブラック ボックスの状態で学習する人もいます。dp 配列の意味がわからず、なぜこのように初期化されるのか理解していません。再帰式を暗記し、トラバース順序を習慣的に記述します。そして、コードを一気に記述します。コードが成功すれば、すべて問題ありません。そうでない場合は、自分の感覚に基づいて変更を加えます。

これは非常に悪い習慣です!

動的調整の質問を行うときは、コードを書く前に dp 配列上の状態転送の特定の状況をシミュレートして、明確なアイデアを念頭に置き、最終結果が目的どおりの結果であることを確認する必要があります。

次にコードを記述します。コードが失敗した場合は、dp 配列を印刷して、事前に推測したものと異なるかどうかを確認します。

出力結果が事前にシミュレートして導出した結果と同じである場合は、再帰式、初期化、またはトラバース順序に問題があります。

事前にシミュレートして導出した結果と異なる場合は、コード実装の詳細に問題があります。

これは、コードに問題が発生した場合に何の手がかりもなくあちこちでランダムに変更を加えるのではなく、完全に考えるプロセスであり、最終的には混乱した状態で失敗したり合格したりします。

これが、動的制御の 5 つのステップで dp 配列を導出することの重要性を強調した理由です。

たとえば、「Code Random Thoughts」チームの WeChat グループでは、一部の学生がコードを通過できないため、ディスカッション グループにコードを投げ込み、「私のコードはソリューションとまったく同じなのに、なぜ通過できないのですか?」と質問します。

このような質問をする前に、実際に次の 3 つの質問について自分で考えてみましょう。

• この問題の状態遷移式を導くための例を示しましたか?
• dp配列をログに記録しましたか?
• 印刷された dp 配列は予想どおりですか?

これら 3 つの自己探求の質問に答えることができれば、問題は基本的に解決されます。あるいは、状態転送を理解していないのか、実装コードの書き方がわからないのか、dp 配列を走査する順序を理解していないのかなど、何が理解できないのかがより明確にわかるようになります。

すると、質問をするときの目的が非常に強くなり、グループ内の友人は質問者の疑問をすぐに理解できるようになります。

これは質問してはいけないという意味ではなく、質問する前によく考えて、要点を押さえた質問をすべきという意味です。

仕事をしてみると、特に大企業では、質問をすることがプロの仕事だということが分かります。そうです、質問をすることはプロ意識を反映するものでもあるのです！

同僚に非常に非専門的な質問をすると、彼らは答えるのが面倒になり、上司はあなたが考える能力に欠けていると考え、それはあなたのキャリア開発に非常に有害です。

したがって、質問を行う際には、専門的な質問をする良い習慣を身に付けるように自分自身を訓練する必要があります。

要約する

この記事は、動的プログラミングの全体的な概要であり、動的プログラミングとは何か、動的プログラミングの問題を解決する手順、デバッグ方法について説明します。

動的プログラミングは非常に大きな分野です。今日の記事では、動的プログラミング シリーズ全体で使用される理論的基礎について説明します。

以降の説明では、具体的な問題について、それに対応する理論的根拠も説明します。例えば、バックパック問題における01バックパック。LeetCodeの問題はすべて01バックパックの応用であり、純粋な01バックパック問題は存在しないため、対応する理論的知識を説明する必要があります。

私が説明する理論的基礎は、教科書に載っているさまざまな動的計画法の定義や複雑な数式ではないことがお分かりいただけると思います。

ここでの理論的基礎はすでに非常に実用的です。各知識ポイントは実際の問題解決に非常に役立つため、誰もが注目する必要があります。