这篇文章上次修改于 899 天前，可能其部分内容已经发生变化，如有疑问可询问作者。 本文共 920 个字，阅读时长 ≈ 3 分钟

AcWing 1015. 摘花生

题面：

Hello Kitty想摘点花生送给她喜欢的米老鼠。

她来到一片有网格状道路的矩形花生地(如下图)，从西北角进去，东南角出来。

地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。

Hello Kitty只能向东或向南走，不能向西或向北走。

问Hello Kitty最多能够摘到多少颗花生。

从左上角往右下角走，只能向下走或向右走，问最多能采到多少花生。很明显是一个数字三角形的模型，因为只有两种走法，状态转移方程为 $\text{f}[i][j]=\max(\text{f}[i-1][j],\text{f}[i][j-1])+a[i][j]$。

标准版代码：

#include<iostream>
using namespace std;
int a[120][120],f[120][120];
int t,r,c;
int main()
{
    cin>>t;
    while(t--){
        cin>>r>>c;
        for(int i=1;i<=r;++i){
            for(int j=1;j<=c;++j) cin>>a[i][j];
        }
        for(int i=1;i<=r;++i){
            for(int j=1;j<=c;++j)
                f[i][j]=max(f[i-1][j],f[i][j-1])+a[i][j];
        }
        cout<<f[r][c]<<endl;
    }
    return 0;
}

那为啥我说这个是标准版呢，因为$\text{f}[i][j]$最小会等于$\text{a}[i][j]$，然后就是看之前的值，所以我们可以直接用$\text{a}$数组来进行动态规划，这样可以省掉一部分空间。

优化版代码：

#include <iostream>
using namespace std;
int t,r,c;
int a[120][120];
int main()
{
    cin>>t;
    while(t--){
        cin>>r>>c;
        for(int i=1;i<=r;++i){
            for(int j=1;j<=c;++j){
                cin>>a[i][j];
                a[i][j]+=max(a[i-1][j],a[i][j-1]);
            }
        }
        cout<<a[r][c]<<endl;
    }
    return 0;
}