问题标题: 酷町堂:最小路径和

0
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
我要回答