线性DP
董晓老师的讲解是从下标0开始算的,其实我们从1开始也可以,我感觉这里从1开始更好理解。是从下往上计算的。j负责列的计算,往上计算时逐步收窄横向的范围,i是纵向的从下往上算,
下面是内存布局
下面是逻辑上的布局
下面的代码是优化之后的代码,正常来说是f数组
存储总和sum,w数组
是存储输入的数字,然后f初始值是0的,每次加上w里面的数,
f [ i ] [ j ] = m a x ( f [ i + 1 ] [ j ] + w [ i ] [ j ] , f [ i + 1 ] [ j + 1 ] + w [ i ] [ j ] ) f[i][j] = max(f[i+1][j] + w[i][j] ,f[i+1][j+1] + w[i][j] ) f[i][j]=max(f[i+1][j]+w[i][j],f[i+1][j+1]+w[i][j])
优化为
f [ i ] [ j ] = m a x ( f [ i + 1 ] [ j ] , f [ i + 1 ] [ j + 1 ] ) + w [ i ] [ j ] f[i][j] = max(f[i+1][j] ,f[i+1][j+1] ) + w[i][j] f[i][j]=max(f[i+1][j],f[i+1][j+1])+w[i][j]
然后发现w数组和f数组作用雷同,直接用f存储输入的三角形,然后累加的时候覆盖上面的值就完事儿了
就直接优化为
f [ i ] [ j ] = m a x ( f [ i + 1 ] [ j ] , f [ i + 1 ] [ j + 1 ] ) + f [ i ] [ j ] f[i][j] = max(f[i+1][j],f[i+1][j+1]) + f[i][j] f[i][j]=max(f[i+1][j],f[i+1][j+1])+f[i][j] ;.
等价于
f [ i ] [ j ] + = m a x ( f [ i + 1 ] [ j ] , f [ i + 1 ] [ j + 1 ] ) f[i][j] += max(f[i+1][j],f[i+1][j+1]) f[i][j]+=max(f[i+1][j],f[i+1][j+1]);
#include<iostream>
#include<algorithm>
#define N 510
using namespace std;
int n;
int f[N][N];
int main(){cin >> n ;for(int i = 1;i <= n; ++i){for(int j = 1; j <= i; ++j){cin >> f[i][j];}}for(int i = n - 1;i >= 1; --i){for( int j = 1 ; j <= i ; ++j){f[i][j] += max(f[i+1][j],f[i+1][j+1]);}}cout << f[1][1];return 0;
}