要注意:起始点是 (1,1)
所以初始化 dp[1][1] = mat[1][1]
为初始合法状态
j = 1时,只有(1,1)是合法状态
j = 2时,(1,2) (2,2) 是合法状态
j = 3时,(1,3) (2,3) (3,3) 是合法状态,依次类推
所以,对行做转移时,要加上这个约束
for(int i = 1;i <= min(j,row);i++)
dp 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 105;
int mat[MAXN][MAXN];
int dp[MAXN][MAXN];
int row,col;
int main(){
cin >> row >> col;
for(int i = 1;i <= row;i++){
for(int j = 1;j <= col;j++){
cin >> mat[i][j];
}
}
// 1,1是初始化合法状态
dp[1][1] = mat[1][1];
//注意剔除不合法的状态
//当初始为1,1时,只能转移到 1,2 2,2这些状态
for(int j = 2;j <= col;j++){
for(int i = 1;i <= min(j,row);i++){
int a = dp[i - 1][j - 1];
int b = dp[i][j - 1];
int c = dp[i + 1][j - 1];
int d = max(a,max(b,c));
dp[i][j] = d + mat[i][j];
}
}
cout << dp[row][col] << endl;
return 0;
}