繰り返しを使用した動的プログラミングの問題

Question

私は繰り返しを使用して動的プログラミングの問題を実装/可視化することについて多くの時間を費やしましたが、理解するのが非常に難しいと思います。メモを使って再帰を使用して、反復まで。

誰かが難しい問題の例やいくつかの基本的な概念を使って同じことを説明することはできますか？行列鎖の乗算のように、最長のパリンドロームの部分配列など。私は再帰プロセスを理解し、効率のために重複しているサブ問題をメモすることができますが、反復を使用して同じことを行う方法を理解できません。

ありがとうございます！

Answer 1

ダイナミックプログラミングは、大きな問題を解決するためにサブ問題を解決することについてすべてです。再帰的アプローチと反復的アプローチの違いは、前者がトップダウンであり、後者がボトムアップであることです。言い換えれば、再帰を使用して、あなたが解決しようとしている大きな問題から始めて、少し小さい問題に切り分けます。あなたが解決できるほど小さな問題に達するまでプロセスを繰り返します。これには、絶対に必要とされる副次的な問題を解決し、メモを使って結果を記憶するだけで済むという利点があります。ボトムアップアプローチは、最初にすべてのサブ問題を解決し、結果を記憶するために表を使用します。必要でない副次的な問題を解決する余分な作業をしていない場合、これはよりよいアプローチです。

もっと簡単な例として、フィボナッチシーケンスを見てみましょう。 F(101)を計算したいとします。再帰的に行うときは、大きな問題（F(101)）から始めます。そのためには、F(99)とF(100)を計算する必要があることがわかります。次に、F(99)についてはF(97)とF(98)が必要です。我々は最小解決可能なサブ問題、すなわちF(1)に達するまで続け、結果をメモする。反復的に行うときは、最小のサブ問題F(1)から始めて、結果をテーブルに保持しています（このため、本質的には1〜101のループで簡単です）。

あなたがリクエストしたマトリックスチェーンの乗算の問題を見てみましょう。素朴な再帰的実装、再帰的DP、そして最後に反復的DPから始めます。これはC/C++スープで実装される予定ですが、あまりよく慣れていなくてもそれに従うことができます。

solve_rn(p, n, 1, n - 1) 

DPのキーではなく、それらを忘れるのサブ問題のすべてのソリューションを覚えているので、我々はドン」：

/* Solve the problem recursively (naive) 

    p - matrix dimensions 
    n - size of p 
    i..j - state (sub-problem): range of parenthesis */ 
int solve_rn(int p[], int n, int i, int j) { 
    // A matrix multiplied by itself needs no operations 
    if (i == j) return 0; 

    // A minimal solution for this sub-problem, we 
    // initialize it with the maximal possible value 
    int min = std::numeric_limits<int>::max(); 

    // Recursively solve all the sub-problems 
    for (int k = i; k < j; ++k) { 
     int tmp = solve_rn(p, n, i, k) + solve_rn(p, n, k + 1, j) + p[i - 1] * p[k] * p[j]; 
     if (tmp < min) min = tmp; 
    } 

    // Return solution for this sub-problem 
    return min; 
} 

結果を計算するためには、我々は大きな問題で始まりますそれらを再計算する必要はありません。それを達成するために、上記のコードにいくつかの調整を行うために些細です：

/* Solve the problem recursively (DP) 

    p - matrix dimensions 
    n - size of p 
    i..j - state (sub-problem): range of parenthesis */ 
int solve_r(int p[], int n, int i, int j) { 
    /* We need to remember the results for state i..j. 
     This can be done in a matrix, which we call dp, 
     such that dp[i][j] is the best solution for the 
     state i..j. We initialize everything to 0 first. 

     static keyword here is just a C/C++ thing for keeping 
     the matrix between function calls, you can also either 
     make it global or pass it as a parameter each time. 

     MAXN is here too because the array size when doing it like 
     this has to be a constant in C/C++. I set it to 100 here. 
     But you can do it some other way if you don't like it. */ 
    static int dp[MAXN][MAXN] = {{0}}; 

    /* A matrix multiplied by itself has 0 operations, so we 
     can just return 0. Also, if we already computed the result 
     for this state, just return that. */ 
    if (i == j) return 0; 
    else if (dp[i][j] != 0) return dp[i][j]; 

    // A minimal solution for this sub-problem, we 
    // initialize it with the maximal possible value 
    dp[i][j] = std::numeric_limits<int>::max(); 

    // Recursively solve all the sub-problems 
    for (int k = i; k < j; ++k) { 
     int tmp = solve_r(p, n, i, k) + solve_r(p, n, k + 1, j) + p[i - 1] * p[k] * p[j]; 
     if (tmp < dp[i][j]) dp[i][j] = tmp; 
    } 

    // Return solution for this sub-problem 
    return dp[i][j];; 
} 

我々としても大きな問題で始まる：

solve_r(p, n, 1, n - 1) 

反復解法が良く、すべての反復だけにあります状態、代わりの先頭から：

/* Solve the problem iteratively 

    p - matrix dimensions 
    n - size of p 

    We don't need to pass state, because we iterate the states. */ 
int solve_i(int p[], int n) { 
    // But we do need our table, just like before 
    static int dp[MAXN][MAXN]; 

    // Multiplying a matrix by itself needs no operations 
    for (int i = 1; i < n; ++i) 
     dp[i][i] = 0; 

    // L represents the length of the chain. We go from smallest, to 
    // biggest. Made L capital to distinguish letter l from number 1 
    for (int L = 2; L < n; ++L) { 
     // This double loop goes through all the states in the current 
     // chain length. 
     for (int i = 1; i <= n - L + 1; ++i) { 
      int j = i + L - 1; 
      dp[i][j] = std::numeric_limits<int>::max(); 

      for (int k = i; k <= j - 1; ++k) { 
       int tmp = dp[i][k] + dp[k+1][j] + p[i-1] * p[k] * p[j]; 
       if (tmp < dp[i][j]) 
        dp[i][j] = tmp; 
      } 
     } 
    } 

    // Return the result of the biggest problem 
    return dp[1][n-1]; 
} 

ちょうどそれを呼び出し、結果を計算する：

solve_i(p, n) 

---

最後の例ではループカウンタの説明：A B C D：

のは、我々は4つの行列の乗算を最適化する必要があるとしましょう。我々は反復的なアプローチをしているので、最初に2の長さのチェーン、すなわち(A B) C D,A (B C) DおよびA B (C D)を計算する。そして、3つの鎖：(A B C) DとA (B C D)。つまり、L、i、およびjが対象です。

Lは（nこの場合4ので、それは3である）、それは2からn - 1に進み、鎖長を表します。

iおよびjは、鎖の開始および終了位置を表す。場合L = 2には、iは1から3に行き、そしてjは2から4に行く：

場合 L = 3に

(A B) C D  A (B C) D  A B (C D) 
^^   ^^   ^^ 
i j    i j    i j 

、iは1から2になり、jは3から4に行く：

(A B C) D  A (B C D) 
^ ^  ^^
i j   i j 

したがって、一般にiは1から0123になります、jはi + L - 1です。

ここでは、(A B C) Dのステップにいると仮定してアルゴリズムを進めていきます。ここでは、すでに計算されているサブ問題（((A B) C) Dと(A (B C)) D）を考慮する必要があります。それはkが対象です。 iとjの間のすべての位置を通過し、サブ問題を計算します。

私は助けてくれることを願っています。

Answer 2

再帰の問題は、プッシュ/ポップする必要があるスタックフレームの数が多いことです。これはすぐにボトルネックになることができます。

フィボナッチシリーズは、反復DPまたはメモとの再帰を使用して計算できます。 DPでF（100）を計算すると、必要なのは長さ100の配列です。 int[100]それは私たちの使用したメモリの勇気です。我々は1と定義されているので、配列事前充填f[0]およびf[1]のすべての項目を計算する。各値は直前の2つに依存します。

再帰的ソリューションを使用する場合は、fib(100)から開始して作業します。 100から0までのすべてのメソッドコールがスタックにプッシュされ、とがメモされているかどうかがチェックされます。これらの操作は加算され、反復にはこれらのいずれも影響を受けません。反復（ボトムアップ）では、以前の回答のすべてが有効であることが既に分かっています。大きな影響はおそらくスタックフレームです。より大きな入力が与えられた場合、反復的なDPアプローチではそれほど些細なことがあったためにStackOverflowExceptionが得られるかもしれません。