$\color{blue}{线性DP}$
状态转移 f(k,i,j) = (i==j)?w[i,k-i]:w[i,k-i]+w[i,k-j]+max(f(k-1,i,j),f(k-1,i-1,j),f(k-1,i,j-1),f(k-1,i-1,j-1))
时间复杂度 $O(n^3)$
$\color{green}{Code-cpp}$
#include<bits/stdc++.h>
#define For(i,x,y) for(int i = x;i<y;++i)
#define _for(i,x,y) for(int i = x;i<=y;++i)
using namespace std;
const int N = 55;
int w[N][N],f[N+N][N][N];
int n,m;
int main(){
scanf("%d%d",&n,&m);
_for(i,1,n)
_for(j,1,m)scanf("%d",&w[i][j]);
_for(k,2,n+m)
_for(i,1,n)
_for(j,1,n)
_for(a,0,1)
_for(b,0,1)
if(i<k&&j<k)f[k][i][j] = max(f[k][i][j],f[k-1][i-a][j-b]+(i==j?w[i][k-i]:w[i][k-i]+w[j][k-j]));
printf("%d",f[n+m][n][n]);
return 0;
}
你这时间复杂度咋胡分析呢?
明明是 $O(n^3)$。
还有,R、C 是什么东西。
额我忘改了
我从别的线性DP题解直接站过来的,时间复杂度忘改了
感谢提醒
别的题的行列
已更正