0
已解决
李显晨
中级启示者
中级启示者
题目描述 Description
小P在一个由m * n块砖铺成的房间中。每块砖上都写上了一个数字。小P现在想从房间的左上角第(0,0)块砖位置开始,走到右下角第(m-1,n-1)的位置,要求经过路径上的数字之和最小,且只能往右和往下走。请你编写一个程序计算出这个最小的数字之和。
输入描述 Input Description
m+1行,第一行两个整数m、n,表示房间的大小
接下来m行,每行n个整数,表示砖块上的数字
输出描述 Output Description
一个整数,表示最小路径和
样例输入 Sample Input
3 4
1 2 3 4
8 7 6 5
1 3 5 7
样例输出 Sample Output
22
数据范围及提示 Data Size & Hint
1<m,n<=20,砖块上的每个数字不超过100
#include<iostream>
#include<algorithm>
using namespace std;
int a[30][30],f[30][30],n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++) cin>>a[i][j];
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];
}
}
cout<<f[n][m];
return 0;
}
样例怎么错了?
0
0
0
汪恺恒
中级启示者
中级启示者
我被这题逼疯了,干脆直接dfs+剪枝
dfs核心
void dfs(int x,int y,int sum){
if(sum>=ans) return ;//最优性剪枝
if(x==n&&y==m){
ans=min(ans,sum);
return ;
}
if(x+1<=n) dfs(x+1,y,sum+a[x][y]);//往下走
if(y+1<=m) dfs(x,y+1,sum+a[x][y]);//往右走
}
注意,ans初值0x3f3f3f3f
主函数
输入
dfs(1,1,0);
结果ans+a[n][m];
(还挺快,最慢的才16ms)
0