题目描述

给定一个棋盘$(n,m)$。

每个格子$(i,j)$有一些价值$w[i][j]$，要求从左上走到右下最多能够获得多少价值。

每次只能选择向下走或者向右走。

题目分析

我们可以用$f[i][j]$用来记录走到$(i,j)$这个格子获得的最大价值。

由于每一次的选择只有两种：向下走或者向右走，很容易想到当前格子的最大价值只能由上面两种状态转移过来。

于是计算方式就是f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j]：要么从$(i,j - 1)$左边走过来，要么从$(i - 1, j)$上面走过来，无论怎么走，都会走到$(i,j)$这个格子，则需要加上$w[i][j]$的价值。

于是最终答案就是$f[n][m]$

闫式DP分析法

状态表示$f[i][j]$：1.属性：从起点出发，走到第$i$行$j$列的所有方案。2.集合：获得的最大价值

状态转移：f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j]

$Code$

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110;

int t, n, m;
int f[N][N];
int w[N][N];

int main()
{
    cin >> t;

    while(t -- )
    {
        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 ++ )
                f[i][j] = max(f[i - 1][j], f[i][j - 1]) + w[i][j];

        cout << f[n][m] << endl;
    }

    return 0;
}