C＃。从左上角到右下角的最小路径 ( n x n ) table

Question

我遇到代码问题，我得到

System.IndexOutOfRangeException

在 find() 方法的第一个循环中。
你们能帮帮我吗？我不知道怎么了。

我找到了 java 的这段代码，并针对 C# 做了一些改动。在 java 代码中有 int[][] A，我将其更改为 int[,]。 P.S java，代码有效。

class Program
{
    static void Main(string[] args)
    {
        int[,] A = { { 1, 7, 9, 2 }, { 8, 6, 3, 2 }, { 1, 6, 7, 8 },
            { 2, 9, 8, 2 } };
        Console.WriteLine("{0}", find(A));
    }

    public static int find(int[,] A)
    {
        int[,] solution = new int[A.Length + 1, A.Length + 1];

        solution[0, 0] = A[0, 0];

        for(int i = 1; i < A.Length; i++)
        {
            solution[0, i] = A[0, i] + solution[0, i - 1]; //IndexOutOfRangeException
        }

        for(int i = 1; i < A.Length; i++)
        {
            solution[i, 0] = A[i, 0] + solution[i - 1, 0];
        }

        for(int i = 1; i < A.Length; i++)
        {
            for(int j = 1; j < A.Length; j++)
            {
                solution[i, j] = A[i, j] 
                    + Math.Min(solution[i - 1, j], solution[i, j - 1]);
            }
        }
        return solution[A.Length - 1, A.Length - 1];
    }
}

Answer 1

问题是在锯齿状数组 ([]) 中，属性 Length 会给你元素的总数，在你的情况下 A.Length == 16 但你只想要一维。解决方案是使用 GetLength.

for (int i = 1; i < A.GetLength(1); i++)

您需要对 X 维度使用 0，对 Y 维度使用 1（[X,Y]）
请参阅 documenation详情。

你的方法应该是这样的：

public static int find(int[,] A)
{
    int[,] solution = new int[A.GetLength(0) + 1, A.GetLength(1)+ 1];

    solution[0, 0] = A[0, 0];

    for (int i = 1; i < A.GetLength(1); i++)
    {
        solution[0, i] = A[0, i] + solution[0, i - 1];
    }

    for (int i = 1; i < A.GetLength(0); i++)
    {
        solution[i, 0] = A[i, 0] + solution[i - 1, 0];
    }

    for (int i = 1; i < A.GetLength(0); i++)
    {
        for (int j = 1; j < A.GetLength(1); j++)
        {
            solution[i, j] = A[i, j]
                + Math.Min(solution[i - 1, j], solution[i, j - 1]);
        }
    }
    return solution[A.GetLength(0) - 1, A.GetLength(1) - 1];
}

C＃。从左上角到右下角的最小路径 ( n x n ) table

C#. Min path from left top corner to right bottom on ( n x n ) table

c#

dynamic-programming

indexoutofrangeexception