動的計画の本質について述べる

前言
前回のダイナミックプランニングの記事では、Fibonacciの例を動的計画に導入し、小銭を両替する例を用いて、動的計画の最も主要な3つの性質を分析しました.

オーバーラップサブ問題

最適サブ構造

状態遷移方程式

しかし、ダイナミックな計画はそれだけではありません.
今日のこの文章では、動的計画に深く入り込み、動的計画の本質を垣間見てみましょう.
動的な計画を徹底的に明らかにするには、避けられない問題は次のとおりです.
再帰、貪欲、記憶化検索と動的計画の間にはいったい何が違うのだろうか.

動的に再帰的に計画されています:単純な空間交換だけですか?いいえ、フィボナの切数列の例はこの観点をよく覆しています.

ダイナミック計画は貪欲:貪欲の強化版だけですか?いいえ、小銭両替の例も同じようにこの観点を覆しています.

では、ダイナミックプランニングの核心は何なのでしょうか.
この質問に答えるには、まず次の質問に答えてみましょう.
いったいどのような問題がダイナミックプランニングに適しているのでしょうか.どのようにDPを鑑定して問題を解くことができますか?
どのような問題がDPで解決できるかを認識すると、DPと他のアルゴリズムの思想の違い、すなわち動的計画の核心を自然に見つけることができると信じています.
ダイナミックプランニングコア
まず、動的計画はある問題にのみ適用され、ある問題の解決方法にすぎないことを明らかにしなければならない.
では、この「ある種の問題」はどんな問題なのでしょうか.
これについて話す前に、コンピュータの本質を少し理解する必要があります.
フォンノイマンアーキテクチャに基づくコンピュータは本質的にステータスマシンであり、なぜそう言うのでしょうか.CPUは計算を行うためにメモリと付き合わなければならない.
メモリにデータが格納されているので(レジスタも外盤も同じです)、データCPUが空気を計算していませんか?従ってメモリは状態(データ)を保存するためのものであり,メモリに現在格納されているすべてのデータが現在の状態を構成しており,CPUは現在の状態を利用して次の状態を計算するしかない.
私たちがコンピュータで問題を処理するのは、変数で状態を格納する方法と、状態間でどのように移行するかを考えているにほかならない.いくつかの変数から別の変数を計算し、現在の状態から次の状態を計算する.
これらに基づいて,評価アルゴリズムの優劣の最も主要な2つの指標も得た.

空間複雑度:計算に必要な記憶状態

をサポートするためである.

時間複雑度:初期状態から最終状態までのステップ

上記の説明がまだはっきりしていない場合は、前のFibonacciの例を挙げてみましょう.

現在のf(n)を計算するには、f(n-1)とf(n-2)を知る必要がある.

次のようになります.

現在の状態f(n)を計算するには、状態f(n-1)とf(n-2)を計算する必要がある.

すなわち,現在の状態は前の2つの状態にのみ関係するため,空間的複雑さについては,前の2つの状態を保存するだけでよい.
これは、動的計画が単純な空間交換ではない理由をよく説明しています.それは実際には状態だけに関係しているからです.
1つの状態から別の状態に移行するのに要する計算時間も定数であるため、線形に増加した状態は、その総時間複雑度も線形である.
以上がダイナミックプランニングの核心です.
状態の定義と状態間の遷移(状態方程式の定義).
では、いわゆる「状態」と「状態間の遷移」をどのように定義するのでしょうか.
ウィキペディアの定義を導入します.
dynamic programming is a method for solving a complex problem by
breaking it down into a collection of simpler subproblems.
それは問題を分割し,問題の状態と状態の関係を定義することによって,問題が繰返し(あるいは分治)で解決できるようにすることである.
紙の上で話をするのは結局浅く感じて、下で私達は更に1本の同様にとても経典の例題を見にきます.
最長増分子シーケンス
これはLeetCode 300番です.
1つの数列を与える、長さはNであり、この数列の最長上昇(増分)サブ数列(LIS)の長さを求める.
例1:

  ：nums = [10,9,2,5,3,7,101,18]
  ：4
  ：         [2,3,7,101]，     4

例2:

  ：nums = [0,1,0,3,2,3]
  ：4
  ：        [0,1,2,3]，     4

状態の定義と状態間遷移の定義をどのように行いますか?
一、状態の定義
まず,問題の分割,すなわち,この問題のサブ問題の定義を行うべきである.
そこで、この問題を再定義します.
長さNの数列が与えられ、
F~k~を、所与の数列におけるk番目の末尾の最長増分子シーケンスの長さとする
F~1~F~N~の最大値を求めます
上の定義は元の問題と同じではないでしょうか.
明らかに両者は等価であるが,明らかに第2の定義の方法では,サブ問題を見つけた.
F~k~にとって、F~1~F~k-1~はいずれもF~k~のサブ問題である.
上記の新しい問題のF~k~を状態と呼ぶ.
F~k~は数列中のk番目の項の末尾のLISの長さである状態の定義である.
二、状態転移方程式の定義
状態を定義した後,状態と状態の関係式を状態遷移方程式と呼ぶ.
この問題はF~k~の定義で言います.
F~k~を、所与の数列におけるk番目の末尾の最長増分子系列の長さとする
思考、状態の間はどのように移るべきですか?
私たちが前に言った分割問題を覚えていますか.ここでは同じように、データを分割することができます.
もし数列が1つしかないとしたら?では、私たちは1に戻るべきです(状態境界の状況を見つけました).
次の状態遷移方程式を書くことができます.
F~1~ = 1
F~k~ = max ( F~i~ + 1 | i ∈(1,k-1))(k > 1)
すなわち、k番目で終わるLISの長さは、max{i番目で終わるLISの長さ+1}であり、i番目はk番目より小さい
みんなは理解して、このような事ではありません～
どうやってやったか思い出してみましょうか?

問題を分割することによって問題(サブ問題)の再定義(状態の定義)を行った.

状態の定義により,状態の境界状況と結びつけて,状態と状態間の遷移,すなわち状態遷移方程式の定義を書いた.

状態遷移方程式を書いたが,これまで動的計画アルゴリズムの核心の思想はすでに表現されている.
あとは記憶的にプッシュ式を解く方法で解決すればいいだけです.
コードを書いてみましょう.
コード#コード#
まずdp配列を定義します.

int[] dp = new int[nums.length];

(ここでdp配列の大きさに注意してください.前の文章を見て小銭を両替する例とは違います.つまり、ここに+1がないので、ここをクリックして次の文章をよく理解してください.)
ここでdp配列の意味は
dp[i]が保存する値は、所与の配列iビットよりも前の最長の増分子シーケンスの長さである.
では、私たちの初期状態は何ですか?
状態の境界状況は次のとおりです.
F~1~ = 1

すなわち、データが1ビットしかない場合、1を返すべきである.

データ個数>1のとき、列全体に2番目の増分数が現れない場合、同様に1.

を返す.
したがって,初期状態はdp配列の各位置に1を与える.

Arrays.fill(dp, 1);

次に、所与の配列の最初の要素、すなわち外層のforループを書き出します.

for(int i = 0; i < nums.length;i++){
        ......
}

私たちの外層がある要素を遍歴したとき、私たちはどうしますか?
この外層元素の前に、それより小さい数が存在するかどうかを探さなければなりません.存在する場合は、この外層元素のdp[i]を更新します.
ある要素の前にそれより小さい数があれば、これはインクリメントサブシーケンスを構成しているのではないでしょうか.
内層forループを書くことができます

for (int j = 0; j < i; j++) {
    //           nums[i]  ，      dp[i] = dp[j] + 1
     if (nums[j] < nums[i]) {
         //      nums[i]            ，       ，          dp[i] 
          dp[i] = Math.max(dp[i], dp[j] + 1);
      }
}

2つのレイヤループが終了すると、dp[]配列に格納されるのは、対応する要素の位置より前の最大インクリメントサブシーケンス長です.dp[]配列を巡って最大値を探すだけで、配列全体の最大インクリメントサブシーケンス長を求めることができます.

 int res = 0;
 for(int k = 0; k < dp.length; k++){
      res = Math.max(res, dp[k]);
 }

この問題のコードも書き終わりました.次は完全なコードを貼ります.

class Solution {
  public int lengthOfLIS(int[] nums) {
      if(nums.length < 2) return 1;
      int[] dp = new int[nums.length];
      Arrays.fill(dp,1);
      for(int i = 0;i < nums.length;i++){
        for(int j = 0;j < i;j++){
          if(nums[j] < nums[i]){
            dp[i] = Math.max(dp[i],dp[j] + 1);
          }
        }
      }
      int res = 0;
      for(int k = 0;k < dp.length;k++){
        res = Math.max(res,dp[k]);
      }
      return res;
  }
}

この問題の2階のforループは以前の両替のコードとほとんど差がなく、前の文章と結びつけて比較して理解することができます.
異なる点は,内層forサイクルの判断条件と状態遷移方程式の表現(dp[]をどのように更新するか)にすぎず,これも動的計画の本質である.
小結
動的計画については多くの誤解と誤解があります.例えば、最もよく見られるのは、空間が時間を変えることであり、貪欲との違いが分からないことです.
この2つのダイナミックプランニングの文章がこれらの誤りを解消し、ダイナミックプランニングの本質をよりよく理解し、状態と状態方程式を理解することを望んでいます.
もちろん、この2つの文章だけではダイナミックな計画を説明するには十分ではありません.だから、リュックサックの問題、石のゲーム、株の問題など、典型的な問題を具体的に説明します.アルゴリズムを学ぶ道を少し曲がってほしいです.
もし皆さんが何か知りたいアルゴリズムとテーマのタイプがあれば、コメントエリアでコメントを教えてください.