2024 年 CSP-S 复赛第二题考察 DP。

题目分析

第二题通常考查 DP 或数据结构，难度中等偏上。

DP 解题四步

  1. 定义状态：dp[i] 表示什么
  2. 状态转移：dp[i] 怎么从 dp[i-1] 得到
  3. 初始状态：dp[0] 是多少
  4. 答案：dp[n] 是答案

常见 DP 模型

  • 线性 DP
  • 区间 DP
  • 背包 DP
  • 树形 DP

优化技巧

  • 滚动数组
  • 前缀和优化
  • 斜率优化

咨询 CSP-S 备赛：151 6522 2880