Recursion to dynamic function

Question

I'm trying to make dynamic function of recursive function and I'm a little bit stuck.

Recursion:

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

Dynamic(all I have so far):

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

And the question is can someone explain to me how do I convert this Math.Min((1 + F(m - 1, n)), Math.Min((1 + F(m, n - 1)), (D(m-1, n-1) + F(m - 1, n - 1)))); code into dynamic? I'm kind of new with recursion.

Answer 1

In the dynamic-programming approach you would use a 2-dimensional lookup table, that you fill in such a way that you always have all data that you need available.

Since you recursion for m and n depends on F(m - 1, n), F(m, n - 1) and F(m - 1, n - 1), all you need to do is make sure that those values are computed already when you start computing F(m, n). For example:

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

I chose the names so that it is easiest to see how it maps to the recursive approach.