Transform recursive method into non-recursive C#

Question

I'm struggling with dynamic programming and desperately need help! I would very appreciate it. For hours I've been trying to transform a recursive method into a non-recursive one, but was unable to do that. My initial task was to write two algorithms for a recurrent equation. The first method being a recursive method, the other using a loop and storing the data.

There are two integers, n and w, and two integer arrays s[n] and p[n]. Need to find the return value of a recursive method G1(n, w) then create method G2(n, w) which would complete the same task, but it has to use loops instead of recursion.

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

I found a possible solution for C#, but I couldn't apply it for my equation:

A similar task (RECURSION)

A similar task (LOOP)

This is my code and initial data, but I can't get it to work:

    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

There is a common solution. You should create a 2D arry by the size of k x r. Then, loop on this array in diagonal zigzag order to fill the value (in bottom-up order, like the following image).

At the end of the filling the value of the 2d array, you will have the value of G2(k,r). You can find the implementation of G2(k,r) in the below.

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