动态规划入门
见到很有意思的问题 : 以往见过许多教材，对动态规划（DP）的引入属于“奉天承运，皇帝诏曰”式：不给出一点引入，见面即拿出一大堆公式吓人；学生则死啃书本，然后突然顿悟。针对入门者的教材不应该是这样的。(看到一位知乎的大佬说的, 深有感悟~)
动态规划 就是 : 给定一个问题，我们把它拆成一个个子问题，直到子问题可以直接解决。然后把子问题的答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法.
那么我们今天就来带给大家 新手入门动态规划的正确方法!
记忆化搜索 = 暴力dfs + 记录答案
动态规划入门思路: dfs暴力 --- 记忆化搜索 --- 递推
1dfs > 2记忆化搜索 > 3逆序递推 > 4顺序递推 > 5优化空间 !
递归的过程:
"递" 的过程是: 分解子问题的过程;
"归" 的过程才是: 产生答案的过程;
"递" -- 自顶向下, "归" -- 自底向上 ， 其中 "底" 是 递归搜索树 的底
写出递推公式的方法:
递推 的公式 = dfs 向下 递归 的公式
递推 数组的初始值 = 递归 的边界
例题
acwing821.跳台阶 \或者\ P1255. 数楼梯
acw1049. 大盗阿福 \或者\ lc198. 打家劫舍
习题
...
用以上思路, 找动态规划的简单题慢慢去写熟练, 熟练之后直接写出递推式即可~
下期待更新的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 好像用不了记忆化搜索？