题目链接
一些话
我也不懂什么叫线性dp，和其他dp不知道有什么区别，做的题太少了。
写博客主要是记录下闫氏dp分析法
切入点
地里每个道路的交叉点上都有种着一株花生苗，上面有若干颗花生，经过一株花生苗就能摘走该它上面所有的花生。
Hello Kitty只能向东或向南走，不能向西或向北走。
问Hello Kitty最多能够摘到多少颗花生。
hk的走法有很多，属于最优解问题，符合dp特征
1≤T≤100
1≤R,C≤100
最多1e2*3,完全够时间，可以dp
流程
// f[i][j]，走法的集合，走到i，j的走法
// 属性是maxn
// 集合划分，最后一个不同的点，f[i][j]可以由上得也可由左得，
// 上：f[i-1][j] + w[i][j]，左：f[i][j-1] + w[i][j];
// 取二者最大
套路
闫氏dp
ac代码
// f[i][j]，走法的集合，走到i，j的走法 // 属性是所有走法的最大花生 // 集合划分，最后一个不同的点，f[i][j]可以由上得也可由左得，取二者最大 #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> using namespace std; const int N = 110; int f[N][N],w[N][N]; int main(){ int t; cin >> t; while(t--){ int n,m; 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; } }
