题目描述
blablabla
样例
blablabla
思路明天早上补
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 500;
int main(){
int n;
cin >> n;
int dp[maxn][maxn], data[maxn][maxn];
memset(dp, 0, sizeof(dp));
memset(data, 0, sizeof(data));
for(int i = 0; i < n; i ++){
for(int j = 0; j <= i; j ++){
scanf("%d", &data[i][j]);
}
}
for(int i = 0; i < n; i ++) dp[n - 1][i] = data[n-1][i];//初始状态
//状态转移
for(int i = n - 2; i >= 0; i --){
for(int j = 0; j <= i; j ++){
dp[i][j] = max(dp[i + 1][j], dp[i + 1][j + 1]) + data[i][j];
}
}
printf("%d\n", dp[0][0]);
return 0;
}