给定一个m行n列的矩阵,从左上角开始每次只能向右或者向下移动,最后到达右下角的位置,路径上的所有数字累加起来作为这条路径的路径和。求所有路径和中最小路径和。
输入格式:
首先输入行数m及列数n,接下来输入m行,每行n个数。
输出格式:
输出第一行为最小路径(假定测试数据中的最小路径唯一),第2行为最小路径和。
输入样例1:
4 4
1 3 5 9
8 1 3 4
5 0 6 1
8 8 4 0
结尾无空行
输出样例1:
1 3 1 0 6 1 0
12
知识点:
思路:
- 大部分求最小(最大)路径和都可以用动态规划进行求解, 用数组dp[][]来存储路径和,
- 因为只能向右和向下进行移动,所以第一行只能是通过向右移动得到的,第一列只能是上一行通过向下得到的(1,1除外)
- 其余情况要取min(dp[i-1][j],dp[i][j-1])的最小值然后加上当前值即dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j]
- 求路径:
- 从dp数组进行确定路径,因为路径中肯定会包括右下角和左上角,其他值是通过下移或者是右移得到的所以要对其进行判断取最小值,然后将其下标变为最小值的下标然后以此类推知道推到(1,1)结束循环(这里也要对第一行第一列进行处理)
注意事项:
- 要考虑到第一行第一例,还有左上角和右下角,然后求路径,要想到路径的获取是从dp中确定的,因为dp中数据不是从有移就是从下移得到的,并且在这里也要考虑到第一行第一列的问题。
源码:
#include<bits/stdc++.h>
using namespace std;
int m, n;
int ans;
int u;
int a[1005][1005];
int dp[1005][1005];
int pre[1005][1005];
void dpsort() {
for (int i = 1;i <= m;i++) {
for (int j = 1;j <= n;j++) {
if (i == 1 && j == 1) {
dp[i][j] = a[i][j];
pre[i][j] = j;
continue;
}
if (j == 1) {
dp[i][j] = dp[i - 1][j] + a[i][j];
pre[i][j] = j;
}
else if (i == 1)
dp[i][j] = dp[i][j - 1] + a[i][j];
else
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + a[i][j];
}
}
}
void path() {
stack<int> st;
st.push(a[m][n]);
int i = m;
int j = n;
while (i != 1 || j != 1) {
if (i == 1) {
st.push(a[i][j - 1]);
j = j - 1;
}
else if (j == 1) {
st.push(a[i - 1][j]);
i = i - 1;
}
else if (dp[i][j - 1] < dp[i - 1][j]) {
st.push(a[i][j - 1]);
j = j - 1;
}
else {
st.push(a[i - 1][j]);
i = i - 1;
}
}
while (!st.empty()) {
int t = st.top();
st.pop();
printf("%d ", t);
}
cout << endl;
}
int main() {
cin >> m >> n;
for (int i = 1;i <= m;i++) {
for (int j = 1;j <= n;j++) {
cin >> a[i][j];
}
}
dpsort();
path();
cout << dp[m][n];
}