问题标题: 酷町堂：4969 英灵殿

4969   英灵殿

经验值：800 时间限制：1000毫秒

题目描述 Description

芬里尔喵终于击败了邪恶的奥丁。他手持着昆古尼尔，在英灵殿中寻找宝物。英灵殿可以看成是一个m*n个格子组成的巨大房间。英灵殿的宝器太多了，芬里尔喵给每个格子的宝器分配了一个价值，w[i][j]。芬里尔喵最初处在巨大房间的左上角，她朝着右下角的出口寻觅。由于英灵殿的魔法力量的封印，她每次只能朝右方或者下方前进。请你帮她计算一下，最后总共最多能获得的宝器的价值是多少。

输入描述 Input Description

第一行，两个整数，m n
接下来m行，第i行有n个空格隔开的整数，第j个值表示w[i][j]

输出描述 Output Description

最多能获得的宝器的总价值

样例输入 Sample Input

5 5 1 5 4 10 15 2 32 6 8 17 15 26 3 18 34 3 6 9 12 16 1 21 10 4 16

样例输出 Sample Output

151

数据范围及提示 Data Size & Hint

m, n<=10

 

//CODE
//#pragma GCC optimize(3)
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
using namespace std;
int n, m;
int w[20][20], f[20][20];
int main() {
//  freopen ("题目名.in", "r", stdin);
//  freopen ("题目名.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> w[i][j];
        }
    }
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            if (i == n) {
                f[i][j] += f[i + 1][j] + w[i][j]; 
            }
            if (j == m) {
                f[i][j] += f[i][j + 1] + w[i][j];
            }
            else {
                f[i][j] += max(f[i + 1][j], f[i][j + 1]) + w[i][j];
            }
        }
    }
    cout << f[n][m];
//  fclose (stdin);
//  fclose (stdout);
    return 0;//好习惯！
}

 

完，递推都忘了，输出32