c# - 将递归方法转换为非递归 C#

Question

我正在为动态规划苦苦挣扎，迫切需要帮助!我将不胜感激。几个小时以来，我一直在尝试将递归方法转换为非递归方法，但无法做到这一点。我最初的任务是为循环方程编写两个算法。第一种方法是递归方法，另一种方法使用循环并存储数据。

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

我找到了 C# 的可能解决方案，但我无法将其应用于我的等式:

A similar task (RECURSION)

A similar task (LOOP)

这是我的代码和初始数据，但我无法让它工作:

    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

有一个通用的解决方案。您应该创建一个大小为 k x r 的二维数组。然后，以对角之字形顺序循环此数组以填充值(按自下而上的顺序，如下图所示)。

在二维数组的值填充结束时，您将得到 G2(k,r) 的值。您可以在下面找到 G2(k,r) 的实现。

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