递归动态函数

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]; 
} 

我选择了名称，以便查看它如何映射到递归方法。