c# - 关于找到解决此问题的标准制表方法的任何建议

Question

我有这个问题:

给定一个正数网格，从 0,0 开始到 n,n 结束。只向右和向下移动。查找数字总和最大的路径。

输入示例:

5 1 2

6 7 8

1 4 9

输出示例:35

我在很多情况下都解决了这个问题，例如我写了一个简单的方程来获得最大路径长度，然后做出一些决定以获得正确的结果。

但是这个例子很容易得到，它应该使用动态规划来解决，因为它是递归的，并且有一些重叠，空间很小:

                                       fn(0,0)
                            fn(0,1)            f(1,0)
                       f(0,2)    f(1,1)     f(2,0) f(1,1)

我使用内存技术轻松解决了这个问题:

       public int GetMaxPathTopDown(int r, int c, int[,] arr, int[,] mem)
    {
        if (r >= arr.GetLength(0) || c >= arr.GetLength(1))
        {
            return 0;
        }

        // Base Case
        if (r == arr.GetLength(0) - 1 && c == arr.GetLength(1) - 1)
        {
            return arr[r, c];
        }

        if (mem[r, c] != -1)
        {
            return mem[r, c];
        }

        int firstPath = GetMaxPathTopDown(r, c + 1, arr, mem);
        int secondPath = GetMaxPathTopDown(r + 1, c, arr, mem);
        return mem[r, c] = arr[r, c] + Math.Max(firstPath, secondPath);
    }

但我想找到标准解决方案来使用制表法解决它。我尝试了很多解决方案，但我认为这不是一种正确的制表方式，所以有什么帮助吗？

Answer 1

@Marzouk，你可以试试这个:

dp[i, j] 将是从 (0, 0) 到 (i, j) 的最大总和.现在，dp[i, j] 将依赖于 dp[i - 1, j] 和 dp[i, j - 1]。因此，重复将是:

dp[i, j] = max(dp[i - 1, j], dp[i, j - 1]) + mt[i, j]

您需要在此处处理极端情况(i = 0 或 j = 0)。

using System;

class MainClass {
  public static void Main (string[] args) {
    int[,] mt = new[,] { {5, 1, 2}, {6, 7, 8}, {1, 4, 9} };
    int[,] dp = new[,] { {0, 0, 0}, {0, 0, 0}, {0, 0, 0} };

    int R = mt.GetLength(0);
    int C = mt.GetLength(1);
    for (int i = 0; i < R; i++)
    for (int j = 0; j < C; j++) {
        dp[i, j] = mt[i, j];
        if (i > 0 && j > 0) {
            dp[i, j] += Math.Max(dp[i - 1, j], dp[i, j - 1]);
        } else if (i > 0) {
            dp[i, j] += dp[i - 1, j];
        } else if (j > 0) {
            dp[i, j] += dp[i, j - 1];
        }
    }

    Console.WriteLine(dp[R-1, C-1]);
  }
}