c# - 递归到动态函数

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

我选择这些名称是为了最容易看出它是如何映射到递归方法的。