二维DP

HDU 2845

一种思路：先转化为一行的dp在转化为一列的dp

#include <cstring>
#include <cstdio>
#include <iostream>
using namespace std;
const int M=2e5+10;
int dp1[M],dp3[M];
int n,m;
int maxx(int a,int b) {
    return a>b?a:b;
}
int main() {
    while(~scanf("%d%d",&n,&m)) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                int x;
                scanf("%d",&x);
                if(j-2>=1) {
                    dp1[j]=maxx(dp1[j-2]+x,dp1[j-1]);
                }else {
                    dp1[j]=maxx(x,dp1[j-1]);
                }
            }
            if(i-2>=1) {
                dp3[i]=maxx(dp3[i-2]+dp1[m],dp3[i-1]);
            }else {
                dp3[i]=maxx(dp1[m],dp3[i-1]);
            }
        }
        printf("%d\n", dp3[n]);
    }
    return 0;
}