TB椰程 TypeBuddy 打字搭子

DP 初始化与边界

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

初值决定转移含义，边界先填好再递推

  • 动态规划
  • DP初始化

前置内容

正文

// DP 初始化：别漏边界
// 初值决定转移含义
// 求最大常设 -INF，求最小设 INF
// 边界先填好再递推
#include <cstdio>
int f[1005][1005];
int n, m;
int main() {
    scanf("%d%d", &n, &m);
    // 全清为很小（负无穷）
    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m; j++)
            f[i][j] = -1e9;
    // 起点边界：从 (1,1) 出发
    f[1][1] = 0;
    // 转移时取更大值
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (i > 1 || j > 1)
                f[i][j] = (f[i - 1][j]
                    > f[i][j - 1]
                    ? f[i - 1][j]
                    : f[i][j - 1]) + 1;
    printf("%d", f[n][m]);
    return 0;
}

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

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