再帰的メソッドを非再帰的Cに変換する

Question

私は動的プログラミングに苦労しており、必然的に助けが必要です！私はとても感謝しています。何時間も私は再帰的メソッドを非再帰的メソッドに変換しようとしていましたが、それを行うことはできませんでした。私の最初の仕事は、反復方程式の2つのアルゴリズムを書くことでした。最初の方法は再帰的方法であり、もう1つはループを使用してデータを保存する方法です。

は二つの整数、NおよびW、および2つの整数列S [N]及びp [N]があります。再帰的メソッドG1（n、w）の戻り値を見つけ、同じタスクを完了するメソッドG2（n、w）を作成する必要がありますが、再帰の代わりにループを使用する必要があります。

private static int G1(int k, int r) 
    { 
     if (k == 0 || r == 0) 
     { 
      return 0; 
     } 

     if (s[k - 1] > r) 
     { 
      return G1(k - 1, r); 
     } 

     return Max(G1(k - 1, r), p[k - 1] + G1(k - 1, r - s[k - 1])); 
    } 

私はC＃のための可能な解決策を見つけたが、私は私の式のためにそれを適用することができませんでした：

A similar task (RECURSION)

A similar task (LOOP)

これは私のコードと初期データであり、私はそれを働かせることができません：

n = 3; 
    w = 3; 

    s = new List<int>{ 2, 3, 8 }; 
    p = new List<int> { 1, 3, 5 }; 

    private static int G2(int k, int r) 
    { 
     List<Tuple<int, int, int>> data = new List<Tuple<int, int, int>>(); 
     data.Add(new Tuple<int, int, int>(0, 0, 0)); 

     do 
     { 
      if (data[0].Item1 == 0 || data[0].Item2 == 0) 
      { 
       data[0] = new Tuple<int, int, int>(data[0].Item1, data[0].Item2, 0); 
      } 

      else 
      { 
       if (s[data[0].Item1 - 1] > data[0].Item2) 
       { 
        data.Add(new Tuple<int, int, int>(data[0].Item1 - 1, data[0].Item2, data[0].Item3)); 
       } 

       if (data[0].Item1 + 1 >= k) 
       { 
        data.Add(new Tuple<int, int, int>(data[0].Item1 - 1, data[0].Item2, data[0].Item3)); 
       } 

       if (data[0].Item2 + 1 >= r) 
       { 
        data.Add(new Tuple<int, int, int>(data[0].Item1 - 1, data[0].Item2 - s[data[0].Item1 - 1], data[0].Item3 + p[data[0].Item1 - 1])); 
       } 
      } 

      Console.WriteLine($"DEBUG: current k: {data[0].Item1} current r: {data[0].Item2} current result: {data[0].Item3}"); 
      data.RemoveAt(0); 

     } while (data.Count > 0 && data.Count(entry => entry.Item1 == k && entry.Item2 == r) <= 0); 


     return data.First(entry => entry.Item1 == k && entry.Item2 == r).Item3; 
    } 

Answer 1

一般的な解決策があります。 k x rのサイズで2D arryを作成する必要があります。次に、この配列を斜めジグザグの順序でループして、値を塗りつぶします（次の画像のようにボトムアップ順）。 2次元配列の値を埋めるの終わりに

は、あなたが G2(k,r)の値を持つことになります。 G2(k,r)の実装は以下で見つけることができます。

int G2(int k, int r) 
{ 
    int[,] values = new int[k + 1,r + 1]; 
    var maxDim = Max(k + 1,r + 1); 
    for(int h = 1 ; h < maxDim * 2 ; h++) { 
     for(int j = 0 ; j <= h ; j++) { 
      int i = h - j; 
      if(i <= k && j <= r && i > 0 && j > 0) { 
       if (s[i - 1] > j) 
       { 
        values[i,j] = values[i - 1, j]; 
       } 
       else 
       { 
        values[i,j] = Max(values[i - 1, j], p[i - 1] + values[i - 1, j - s[i - 1]]); 
       } 
      } 
     } 
    } 
    return values[k , r]; 
}