矩阵行走
题目ID：6086必做题100分
最新提交：
Wrong Answer
0 分
历史最高：
Wrong Answer
0 分
时间限制: 1000ms
空间限制: 65536kB
题目描述
【问题描述】
给定一个 n×n 的矩阵 A，其中每个元素都是非负整数。从矩阵的左上角出发，每次只能向右或向下移动一格，直到到达矩阵的右下角。请找出一条从左上角到右下角的路径，使得路径上经过的元素之和最小。
【输入描述】
第一行输入一个整数 n(1≤n≤1000)代表矩阵的行列数。接下来有 n 行，每行有 n 个整数 ai(ai>0,ai<10^9)
【输出描述】
输出一个整数，代表最小的元素和（注意数据范围）。
【样例输入】
3
1 2 3
4 5 6
7 8 9
【样例输出】
21
【样例解释】
从左上角到右下角的路径有多种，它们的经过的元素之和分别为：
1+2+3+6+9=21
1+2+5+6+9=23
1+2+5+8+9=25
1+4+5+6+9=25
1+4+5+8+9=27
1+4+7+8+9=29
因此，经过的元素之和最小的路径是第一条路径，其经过的元素之和为 21。
3 个赞
林子熙1
(good)
3
代码
小小dfs直接那下
int ans=1e9;
void dfs(int x,int y,int s){
if(s>ans)return;
if(x==n&&y==n)ans=min(ans,s);
dfs(x+1,y,s+a[x+1][y]);
dfs(x,y+1,s+a[x][y+1]);
}
3 个赞
林子熙1
(good)
4
写错了
小小dp直接那下
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+a[i][j];
}
}
2 个赞
江禹睿
(January)
7
试一试递推（有人也称DP，戳一下）。要建一个递推二维数组。因为每一个点（第一行的第一个除外）都是从上或左过来的，所有，求上面的数（或左边的数）+此格的数字，并保留最小值。做后输出第n行的第n个。（个人意见，不喜勿喷）
3 个赞
最短路线公式：for(int i=n+1;i<=n+m;i++) ans=ans*i/(i-n);
直接AC
1 个赞