动态规划做题步骤
- 重述问题
- 找到最后一步
- 去掉最后一步，是否能划分出子问题
- 考虑边界
下期待更新的dp题单（2024.2.25编）
LCR 091. 粉刷房子 简单dp
413. 等差数列划分 如果满足等差，则f[i] = f[i - 1] + 1, 否则为0
279. 完全平方数 简单预处理，最后一步：选择某个数作为最后一个
91. 解码方法 正序dfs好写
646. 最长数对链 最长上升子序列模板 + 排序
918. 环形子数组的最大和 找找最大和 、 最小和 和 总和的关系
376. 摆动序列 考虑相邻两个数大小问题，枚举选哪个模型，dp转移可以直接01转移
2786. 访问数组中的位置使分数最大 枚举每个数选或不选，记录上的数的奇偶性，01转移 实现dfs不需要传vector的参数
213. 打家劫舍 II 考虑选不选第一个物品，可以把问题分为两个子问题
122. 买卖股票的最佳时机 II 状态机模型
368. 最大整除子集 pre数组记录路径，更新时实现记录，而不是以前的max不知道更新没更新
1105. 填充书架 枚举选哪个，转移方程有教学意义
1416. 恢复数组 枚举选哪个，集合转移
1043. 分隔数组以得到最大和 枚举选哪个，集合转移
2400. 恰好移动 k 步到达某一位置的方法数目 要对mem数组做偏移，mem[now + N][cnt] ，选其中一个的思路
1335. 工作计划的最低难度 枚举选哪个思路，集合转移
7006. 销售利润最大化 集合转移， 预处理endi，选或不选
2008. 出租车的最大盈利 选或不选
1235. 规划兼职工作 选或不选 1751. 最多可以参加的会议数目 II 类似 2054. 两个最好的不重叠活动
01转移
376. 摆动序列 考虑相邻两个数大小问题，枚举选哪个模型，dp转移可以直接01转移
2786. 访问数组中的位置使分数最大 枚举每个数选或不选，记录上的数的奇偶性
122. 买卖股票的最佳时机 II 状态机模型
1186. 删除一次得到子数组最大和 子数组最大和 + 记录删没删
2369. 检查数组是否存在有效划分 划分型dp 好像用不了记忆化搜索？