今日刷题量：3
当前刷题总量：130
Easy: 59
Mid: 64
Hard: 7
Day32
基础理论
如果题目大致符合这些特征，可以优先往dp上想：
- 求最值/计数/可行性：最大值、最小值、方案数、是否能做到……
- 问题可以拆成子问题：整题答案可以由更小规模的“类似问题”组合出来。
- 子问题会重复出现：比如「前 i 个」的各种情况，或者某个状态会被多次用到。
- 约束规模：
- n <= 1e3/1e4 且暴力明显超时 → 很有可能是 DP
- n <= 2^20 左右，有“子集”、“选择若干” → 可能是状态压缩 DP
动态规划五步曲：
1.确定dp数组（dp table）以及下标的含义
dp[状态]表示某种含义，常见方式如下：
-
一维：dp[i] 表示：考虑前 i 个元素时，能得到的某个最值/计数
- 例：爬楼梯：dp[i] = 到第 i 级台阶的方案数
-
二维：dp[i][j] 表示：考虑前 i 个元素，当前某个“资源/限制”为 j 时的答案
- 例：0-1 背包：dp[i][w] = 前 i 件物品，背包容量为 w 的最大价值
-
区间类：dp[l][r] 表示：区间 [l, r] 上的最优值/方案数
-
状态压缩：dp[mask]、dp[i][mask]：mask 是一个 bitmask，表示某些元素的选/不选、某些位置的状态。
2.确定递推公式
写出状态转移，思考当前状态从哪些上一个状态转移过来
列举所有可能的决策：
- 选 / 不选
- 从哪里转移过来
- 合并哪两个区间
- 转到哪一个子集
注意处理无效状态：
- 一般会初始化为 -INF / INF，或者用布尔数组标记某状态是否可达
3.dp数组如何初始化
核心确定初始化和边界条件
-
找到最小子问题，把它的值写死：
- 从 0 开始：f[0] = 0 / 1 等
- 从空集开始：f[0] = ...
- 从单个元素开始：f[i][i] = base（区间 DP）
-
另外比如：
- 当 j（比如容量）为 0 时，啥意思？背包体积为 0，只能装 0 价值 → f[*][0] = 0
- 当 mask = 1<<start 时，路径从起点出发。
- 可以把 DP 表画个小样（比如 i, j 不超过 3~4），手算几格，对照转移是否成立。
4.确定遍历顺序
遍历顺序要配合转移依赖：
- 如果 f[i] 依赖 f[i-1]、f[i-2]，那 i 从小到大。
- 区间 DP：len 从小到大，l 从 1 到 n-len+1，r = l+len-1。
5.举例推导dp数组
练习题目
509. 斐波那契数（easy）：https://leetcode.cn/problems/fibonacci-number/description/
70. 爬楼梯（easy）：https://leetcode.cn/problems/climbing-stairs/description/
746. 使用最小花费爬楼梯 （easy）：https://leetcode.cn/problems/min-cost-climbing-stairs/description/
复习
数组part1