欢迎关注

分析

我们把走到一个点看做一个状态，对$HelloKitty$来说，走到一个点只有两种方式，一种是从上面（北面）走到该点，另一种是从左边（西面）走到该点。要到达点$(i,j)$，要么是从$(i-1,j)$走到$(i,j)$，要么是从点$(i,j-1)$走到$(i,j)$。所以从哪个点走到(i,j)就是一个决策。

接下来，我们用$f[i][j]$来代表走到点$(i,j)$一共摘到的花生。我们需要走到$(n,m)$，所以可以得到状态转移方程: $f[i][j] = min(f[i-1][j]),f[i][j-1]))+a[i][j]$。根据转移方程，我们可以推出走到$(n,m)$处摘到的最多花生。

C++ 代码

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int a[105][105], f[105][105];

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(a, 0, sizeof(a));
        memset(f, 0, sizeof(f));
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                scanf("%d", &a[i][j]);
            }
        }
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                f[i][j] = max(f[i][j - 1], f[i - 1][j]) + a[i][j];
            }
        }
        printf("%d\n", f[n][m]);
    } 
    return 0;
}