返回上一级检索目录 《动态规划（算法提高课）》

数字三角形模型

相关题目

模板题

AcWing 898. 数字三角形

变式与应用

AcWing 1018. 最低通行费

AcWing 1027. 方格取数

AcWing 275. 传纸条

分析

状态转移方程
$$ f[i,j] = \max(f[i-1,j-1],f[i-1,j])+a[i,j] $$

代码模板

f[1][1] = a[1][1];
for (int i=2; i<=n; i++) {
    for (int j=1; j<=i; j++) {
        f[i][j] = max(f[i-1][j-1],f[i-1][j])+a[i][j];
    }
}