穿越矩阵(15分)动态规划

题目内容：

 现在有一个 m * n 的整数矩阵，请你编写一个程序计算出一条从左到右穿过矩阵的路径，并使此路径的费用最小。路径从矩阵的左侧的第一列的任意单元格开始，逐步穿过矩阵到达最右侧的一列的任意单元格。每一步是指从某单元格进入它一列的相邻单元格（如下图，可以是横向或斜向）。矩阵的第一行和最后一行实际是相邻的，你可以想象矩阵是包裹在一个横放的圆柱体外面（这点很重要）。

路径的花费是指这条路径所穿越的所有单元格中的数字之和。

输入描述

输入包括一系列矩阵描述。每个矩阵描述的第一行是 m 和 n，即矩阵的行数和列数；之后的 m 行，每行包括 n 个以空格分开的整数，则是当前矩阵的值，注意矩阵的值未必是正数。

矩阵的行数 m 和列数 n 的范围是：1 <=m<=10、 1<=n<=100；所有路径的费用值都可以用 30bit 的整数表示。

 

输出描述

针对每一个矩阵，找出费用最小的路径，并将其输出。每个矩阵的输出包括两行，第一行是路径本身，即输出每一步所在的行，第二行则是该路径的费用。

如果对于同一个矩阵有多条不同的费用最小路径，则输出左端行号较小的一条。

 

输入样例

5 6

3 4 1 2 8 6

6 1 8 2 7 4

5 9 3 9 9 5

8 4 1 3 2 6

3 7 2 1 2 3

 

输出样例

1 2 1 5 4 5

11

1.关于为什么要从最右边找到最左边

    如果从左边找到右边，因为你不知道后面的哪一个加到最后之后会最小，万一当前选的最小的加到最后并不是最小的呢？如果从最右边倒着找，你每次找的最小的可以往前推出一整组最小的。

2.关于选择一个点的右上、右、右下的问题(越界)

    右上：横坐标i+1、纵坐标(j+1) % n

    右：横坐标i+1、纵坐标j

    右下：横坐标i+1、(j-1+n) % n

dp[j][i] += min(min(dp[j][i + 1], dp[(j + 1) % n][i + 1]), dp[(j - 1 + n) % n][i + 1]);

3.关于如何保存路径的问题

    当求出总路程最小的min时，记录其所在行，从该行起，往后找，题目数据第一个点是（0,0），从（0,0）开始找右上(4, 1)、右(0, 1)、右下(1,1).

    有一个关系可以确定右上、右、右下哪个点在是我们确定的最小min的路线中

dp[i][j] - a[i][j] == dp[(i + q[k] + n) % n][j + 1]

如果找到该点，则再从该点找右上、右、右下，重复此步骤知道找到最后一列。

AC代码

#include <iostream>
using namespace std;

int a[11][101] = { 0 }, dp[11][101] = { 0 };
int path[11] = { 0 };//记录最后结果路径
int q[3] = { 1, -1, 0 };

int min(int a, int b) {
	return a < b ? a : b;
}

int main() {
	int m, n;
	while (cin >> n >> m) {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				cin >> a[i][j];

		for (int i = 0; i < n; i++)
			dp[i][m - 1] = a[i][m - 1];

		//从m-2开始的原因是从m-1在上面dp=a;
		for (int i = m - 2; i >= 0; i--)
			for (int j = 0; j < n; j++)
			{
				dp[j][i] = a[j][i];
				dp[j][i] += min(min(dp[j][i + 1], dp[(j + 1) % n][i + 1]), dp[(j - 1 + n) % n][i + 1]);//判断右上、右、右下三个点
			}

		int min = dp[0][0];
		int pos = 0;
		for (int i = 1; i < n; i++)
			if (min > dp[i][0])
			{
				min = dp[i][0];
				pos = i;
			}//找到最小的min路线耗费
		path[0] = pos + 1;

		for (int j = 0; j < m; j++)
		{
			int i = pos;
			for (int k = 0; k < 3; k++)//三次表示：右下、右上、右
				if (dp[i][j] - a[i][j] == dp[(i + q[k] + n) % n][j + 1])//确定某个点是不是我们找min所需要的点
				{
					path[j + 1] = (i + q[k] + n) % n + 1;
					pos = path[j + 1] - 1;//确定该点是，就从该点开始找右下、右上、右，故需后来需要i = pos.
					break;
				}
		}
		int i = 0;
		for (i = 0; i < n; i++)
			cout << path[i] << " ";
		cout << path[i] << endl;
		cout << min << endl;
	}
	return 0;
}