1015. 摘花生

题目传送门

一、提高课学习思路

其实，本质上就是知识图谱，闫老师写了这个软件，要擅于使用：

AC Saber

当前：\(AcWing\) \(1015\) 摘花生

前序：

二、闫式DP分析法

\(Q\):\(dp\)为什么能优化算法呢？

\(A\):因为它是枚举了所有方案，它枚举的比较聪明。暴搜是枚举每一种方案，它的算法复杂度是指数级别的。\(DP\)之所以能优化，是因为它用了一个数来表示一类东西。就是状态\(f[i][j]\)可以来表示一类东西，每一次都是在集合基础之上做出选择，而不是一事一议。

三、使用闫式DP分析法分析本题

本题的集合含义\(f[i][j]\)来表示所有从\((1,1)\)走到\((i,j)\)的路线,\(f[i][j]\)的值：所有路线中花生数量之和最大值。

对比一下：

传统方式：从\((1,1)\)走到\((i,j)\)的最大值。

闫氏\(DP\)思考法：从\((1,1)\)走\((i,j)\)所有路线的最大值。

总结一下，就是多了一个中间的集合状态，所有路线，但就是因为增加了这个中间的集合，使得下一步的分析工作变得有决策性，而不是一事一议，牛就牛在这里！

结果：就是\(f[n][m]\)就是解

四、实现代码

#include 

using namespace std;
const int N = 110;
int w[N][N]; //(i,j)位置花生的数量
int f[N][N];
int T;//一共有T组数据
int n, m;

int main() {
    //优化输入
    ios::sync_with_stdio(false);
    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];

        //base case,这个不写也行，因为f[0][1],f[1][0]都是0嘛~
        //f[1][1] = w[1][1];

        //dp开始，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];

        printf("%d \n", f[n][m]);
    }
    return 0;
}