欧拉项目 | 82题 | 三方向的最小和路径

原题链接

从矩阵的左边一行的任意一个元素开始，可以往上、往下、往右前进，到达最右边的某个元素为止。由此形成了一条路径，要求使得该路径上的数字之和最小。

题中的5 * 5的矩阵可以用于测试和debug，最后要求给出答案的是一个80 * 80的矩阵。

这是一道典型的动态规划题目。

初始化一个80 * 80的二维数组用于保存结果。第一列就是矩阵的第一列。

然后从j - 1列向j列前进。
考虑第i行，可以是从j - 1列的任何一个位置k向上或者向下到达第i行，然后向右平移过来，选择和最小的记录在第j列第i行。
三层循环，将80 * 80的二维数组填满。

最后要的最小路径和就是最后一列值最小的一个数字。
整个题目不难，代码如下：

long[,] sums = new long[dim, dim];

for (int i = 0; i < dim; i++)
{
	sums[i, 0] = matrix[i, 0];
}

for (int j = 1; j < dim; j++)
{
	// from column j-1 to column j
	for (int i = 0; i < dim; i++)
	{
		// consider row i
		long min = long.MaxValue;
		for (int k = 0; k < dim; k++)
		{
			long temp = sums[k, j - 1] + matrix[i, j];
			int begin = 0;
			int end = 0;
			if (k < i)
			{
				begin = k + 1;
				end = i;
			}
			else
			{
				begin = i;
				end = k - 1;
			}
			for (int index = begin; index <= end; index++)
			{
				temp += matrix[index, j - 1];
			}

			if (temp < min)
			{
				min = temp;
			}
		}

		sums[i, j] = min;
	}
}

var lastColumn = new List<long>();
for (int i = 0; i < dim; i++)
{
	lastColumn.Add(sums[i, dim - 1]);
}

return lastColumn.Min();