程序填空题：求解矩阵最小路径和问题（动态规划）

给定一个m行n列的矩阵，从左上角开始每次只能向右或者向下移动，最后到达右下角的位置，路径上的所有数字累加起来作为这条路径的路径和。求所有路径和中最小路径和。

```c++
#include
#include
#include
#include
#include
using namespace std;
#define MAXN 100
int a[MAXN][MAXN];
int n,m;
int ans=0;
int dp[MAXN][MAXN];
int pre[MAXN][MAXN];

void minpath();//求最小和路径ans
void Disppath();//输出最小和路径

int main()
{ memset(pre,0,sizeof(pre));
memset(dp,0,sizeof(dp));
scanf("%d%d",&m,&n);
for (int i=0;i for (int j=0;j scanf("%d",&a[i][j]);
minpath();
Disppath();
printf("\n%d",ans);
return 0;
}

void minpath() //求最小和路径ans
{ int i,j;
dp[0][0]=a[0][0];
for(i=1;i { dp[i][0]=;
pre[i][0]=0;
}
for (i=1;i { dp[0][i]=;
pre[0][i]=1;
}
for(i=1;i { for(j=1;j { if(dp[i][j-1] { pre[i][j]=1;
dp[i][j]=;
}
else
{ pre[i][j]=0;
dp[i][j]=;
}
}
}
ans=;
}

void Disppath() //输出最小和路径
{ int i=m-1,j=n-1;
stack path;
while (true)
{ path.push(a[i][j]);
if(i==0&j==0)break;
if(pre[i][j]==1) j--;
else i--;
}
while(!path.empty())
{printf("%d ",path.top()); path.pop();}
}
```
### 输入格式:
首先输入行数m及列数n，接下来输入m行，每行n个数。

### 输出格式:

输出第一行为最小路径（假定测试数据中的最小路径唯一），第2行为最小路径和。

### 输入样例1:

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

### 输出样例1:

```out
1 3 1 0 6 1 0
12
```





答案：
第1空：dp[i-1][0]+a[i][0]

第2空：a[0][i]+dp[0][i-1]

第3空：a[i][j]+dp[i][j-1]

第4空：a[i][j]+dp[i-1][j]

第5空：dp[m-1][n-1]