遞歸動態函數

Question

我正在嘗試使遞歸函數的動態函數，我有點卡住了。

遞歸：

static int F(int m, int n) 
    { 
     if(n == 0) 
      return m; 

     if (m == 0 && n > 0) 
      return n; 

     else 
      return Math.Min((1 + F(m - 1, n)), Math.Min((1 + F(m, n - 1)), (D(m-1, n-1) + F(m - 1, n - 1)))); 
    } 

    static int D(int i, int j) 
    { 
     Console.WriteLine("i:{0} | j:{1}", i, j); 
     if (x[i] == y[j]) 
     { 
      return 1; 
     } 
     return 0; 
    } 

動態（所有我至今）：

static int F2(int m, int n) 
    { 
     if (n == 0) 
     { 
      return m; 
     } 
     if(m==0 && n > 0) 
     { 
      return n; 
     } 
     else 
     { 
      //Math.Min((1 + F(m - 1, n)), Math.Min((1 + F(m, n - 1)), (D(m-1, n-1) + F(m - 1, n - 1)))); 
     } 
    } 

，問題是有人可以給我解釋一下我怎麼轉換這個Math.Min((1 + F(m - 1, n)), Math.Min((1 + F(m, n - 1)), (D(m-1, n-1) + F(m - 1, n - 1))));代碼到動態？我對遞歸有點新。

Answer 1

在動態編程方法中，您可以使用二維查找表，您可以使用這種方式填寫所有需要的數據。

既然你遞歸m和n取決於F(m - 1, n)，F(m, n - 1)和F(m - 1, n - 1)，所有你需要做的是確保當你開始計算F(m, n)這些值已經計算。例如：

static int F2(int M, int N) { 
    var F = new int[M + 1, N + 1]; 

    for (var m = 0; m <= M; m++) { 
     for (var n = 0; n <= N; n++) { 
      if (n == 0) { 
       F[m, n] = m; 
       continue; 
      } 
      if (m == 0 && n > 0) { 
       F[m, n] = n; 
       continue; 
      } 
      F[m, n] = Math.Min((1 + F[m - 1, n]), Math.Min((1 + F[m, n - 1]), (D(m-1, n-1) + F[m - 1, n - 1]))); 
     } 
    } 

    return F[M, N]; 
} 

我選擇了名稱，以便查看它如何映射到遞歸方法。