问题标题: 酷町堂：4400

4400   捡金币经验值：1200

题目描述 Description

小P路过一个N*M个格子大小的房间，房间的每个格子上都放有一定数量的金币。现在小P在这个房间的左上角，只能向下或向右移动，每次移动一格。每次经过某一个格子都可以捡起格子中的金币。
请你帮小P选择一条到达右下角的路，使得在移动的过程中能够捡到最多的金币。

输入描述 Input Description

第一行：N M ，表示房间是由一个N*M的格子组成
接下来有N行：每行有M个正整数，Xi1 Xi2 ……Xim 表示各位置中的金币数（单个空格隔开）

输出描述 Output Description

输出有一个整数， 表示小P捡到最多的金币数

样例输入 Sample Input

3 4 3 1 2 8 5 3 4 6 1 0 2 3

样例输出 Sample Output

24

数据范围及提示 Data Size & Hint

1≤N M≤20，0≤Xij≤500

#include<iostream>
using namespace std;
int m,n,f[1005][1005],a[105][105];
int main(){
    cin>>m>>n;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];
        }
    }
    f[1][1]=a[1][1];
    for(int i=2;i<=m;i++){
        for(int j=1;j<=n;i++){
            if(j==1){
                f[i][j]=f[i-1][j]+a[i][j];
            }
            else f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
        }
    }
    cout<<f[m][n];
    return 0;
}