【算法设计与分析】求解矩阵最小路径和问题-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法设计与分析】求解矩阵最小路径和问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

《算法设计与分析》的实验，稍微记录一下，欢迎讨论。

题目描述

给定一个m行n列的矩阵，从左上角开始每次只能向右或者向下移动，最后到达右下角的位置，路径上的所有数字累加起来作为这条路径的路径和。编写一个实验程序求所有路径和中的最小路径和。例如，一下矩阵中的路径1→3→1→0→6→1→0是所有路径中路径和最小的，返回结果是12：

1	3	5	9
8	1	3	4
5	0	6	1
8	8	4	0

解题思路

将矩阵用二维数组data存放，查找从左上角到右下角的路径，每次只能向右或者向下移动，所以结点（i，j）的前驱结点只有（i，j - 1）和（i - 1，j）两个，前者是水平走向，后者是垂直走向。
用二维数组dp作为动态规划数组，dp[i][j]表示从顶部data[0][0]查找到（i，j）结点时的最小路径和。显然这里有两个边界，即第一列和第一行，达到它们中结点的路径只有一条而不是常规的两条。
状态转移方程如下：
dp[0][0] = data[0][0]
dp[i][0] = dp[i - 1][0] + data[i][0] // 考虑第一列的边界，1 ≤ i ≤ m - 1
dp[0][j] = dp[0][j - 1] + data[0][j] // 考虑第一行的边界，1 ≤ j ≤ n - 1
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + data[i][j] // 其他有两条达到路径的结点

求出的dp[m - 1][n - 1]就是最终的结果。
为了求最小路径和，设计一个二维数组pre，pre[i][j]表示查找到（i，j）结点时最小路径上的前驱结点，由于前驱结点只有水平和垂直两个走向，pre[i][j]根据路径走向取1（水平）或者0（垂直）。
在求出ans后，通过pre[m - 1][n - 1]反推求出反向路径，最后正向输出该路径即可。

参考代码

#include <iostream>
#include <vector>
using namespace std;
#define MAXM 100
#define MAXN 100
// 问题表示
int data[MAXM][MAXN] = {{1, 3, 5, 9}, {8, 1, 3, 4}, {5, 0, 6, 1}, {8, 8, 4, 0}};
int m = 4, n = 4;
// 求解结果表示
int dp[MAXM][MAXN];  // 动态规划数组
int pre[MAXM][MAXN];  // 记录前驱结点
int ans;  // 最小路径长度
// 求最小路径和ans
void miniPath() {
	dp[0][0] = data[0][0];
	for(int i = 1; i < m; i++) {  // 计算第一列的值
		dp[i][0] = dp[i - 1][0] + data[i][0];
		pre[i][0] = 0;  // 垂直路径
	}
	for(int j = 1; j < n; j++) {  // 计算第一行的值
		dp[0][j] = dp[0][j - 1] + data[0][j];
		pre[0][j] = 1;  // 水平路径
	}
	for(int i = 1; i < m; i++) {  // 计算其他的值
		for(int j = 1; j < n; j++) {
			if(dp[i][j - 1] < dp[i - 1][j]) {
				dp[i][j] = dp[i][j - 1] + data[i][j];
				pre[i][j] = 1;
			} else {
				dp[i][j] = dp[i - 1][j] + data[i][j];
				pre[i][j] = 0;
			}
		}
	}
	ans = dp[m - 1][n - 1];
}
// 输出最小路径和
void disPath() {
	int i = m - 1, j = n - 1;
	vector<int> path;  // 存放反向最小路径
	vector<int>::reverse_iterator it;  // 创建迭代器
	while(1) {
		path.push_back(data[i][j]);
		if(i == 0 && j == 0) break;
		if(pre[i][j] == 1) j--;  // 同行
		else i--;  // 同列
	}
	printf("\t最短路径：");
	for(it = path.rbegin(); it != path.rend(); ++it) printf("%d ", *it);  // 反向输出构成正向路径
	printf("\n\t最短路径和：%d\n", ans);  // 输出最短路径和
}

int main (void) {
	miniPath();
	printf("求解结果\n");
	disPath();
	return 0;
}