最少费用 OpenJ_Bailian - 3251

一个商人穿过一个正方形的网格,每经过网格上的一个点需要缴纳一定的费用。每行和每列上的点费用都是按照从小到大顺序排列的,并且对于每个网格上的点,其前后左右的各个点的收费都是不一样的。 
编写程序设计一个商人总左上角走到右下角花费的最小费用。

Input

第一行是一个整数,表示正方行的宽度N (N <100), 
后面n行n列为网格上每个点的费用

Output

一行,表示最小费用

Sample Input

5
1  4  6  8  10 
2  5  7  15 17 
6  8  9  18 20 
10 11 12 19 21 
20 23 25 29 33 

Sample Output

109

Hint

可以用递归方法,或者动态规划方法

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100;
int a[N][N];
int find(int x,int y){
    if(x==0&&y==0) return a[0][0];
    if(x==0) return a[x][y]+find(0,y-1);
    if(y==0) return a[x][y]+find(x-1,0);
    return min(find(x-1,y),find(x,y-1))+a[x][y];
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    cout<<find(n-1,n-1)<<endl;


}

上一篇:机器学习(二)


下一篇:dp - bailian 2749:分解因数