TB椰程 TypeBuddy 打字搭子

数字三角形

CSP-J · 编程模板 · 片段 · cpp · 难度 3/5 · 共 596 字

线性 DP，自底向上取两路较大

  • 动态规划
  • 数字三角形

前置内容

正文

// 数字三角形：线性 DP
// 从顶到任选路走到底部
// 每步向下或右下走
// 状态转移取两路较大
#include <cstdio>
int a[1005][1005], f[1005][1005], n;
int main() {
    scanf("%d", &n);
    // 读入三角形（左下对齐存）
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            scanf("%d", &a[i][j]);
    // 自底向上递推更省事
    for (int i = n; i >= 1; i--)
        for (int j = 1; j <= i; j++)
            // 取下一层两路较大
            f[i][j] = a[i][j] +
                (f[i + 1][j]
                > f[i + 1][j + 1]
                ? f[i + 1][j]
                : f[i + 1][j + 1]);
    // 顶点即答案
    printf("%d", f[1][1]);
    return 0;
}

CSP-J · 编程模板的其它内容

打字首页 · 词库画廊 · 编程打字 · 指法入门 · 天梯榜 · 数据分析 · 班级课堂 · 关于我们
椰程 TypeBuddy 打字搭子 —— 键盘指法练习 · 单词记忆 · 班级课堂 · 在线 PK