动态规划总结
动态规划五部曲
五部曲
- 确定dp数组
- 确定递推公式
- 初始化
- 遍历顺序
- 举例推导
动态规划系列基础问题
- 关于动态规划，你该了解这些！(opens new window)
- 理解动态规划五部曲，利用打印dp数组进行debug。理解是用动态规划问题的一些特点。比如总最优问题能拆出多个最优子问题，各个父子问题之间有递推关系，伴随着状态的转移。
- 动态规划：斐波那契数(opens new window)
- 非常自然的能理解父子问题的存在以及之间的递推关系。
- 动态规划：爬楼梯(opens new window)
- 每次选择爬一步还是两步意味着两种状态，动态规划优化了这个一步步决策的过程，前一爬和后一爬之间有着状态的转移。
- 动态规划：使用最小花费爬楼梯(opens new window)
- 逻辑和上面相同，在选择的时候考虑爬一步花费最少还是爬两步花费最少
- 动态规划：不同路径(opens new window)
- 考虑到达当前位置能有几种选择。
- 动态规划：不同路径还不够，要有障碍！(opens new window)
- 障碍物位置的状态为 0
- 动态规划：整数拆分，你要怎么拆？(opens new window)
- 拆分成2个数以及可以继续拆分的数，两种情况。
- 动态规划：不同的二叉搜索树(opens new window)
- 先确定根节点，根据根节点进行分类讨论状态
背包问题系列
- 动态规划：关于01背包问题，你该了解这些！(opens new window)
- 理解01背包由暴力回溯转化而来。背包容量、物品、重量、价值几个概念
- 动态规划：关于01背包问题，你该了解这些！（滚动数组）(opens new window)
- 背包应当逆序防止被覆盖
- 动态规划：分割等和子集可以用01背包！(opens new window)
- 能否把容量为 sum / 2的背包装满。
- 动态规划：最后一块石头的重量 II(opens new window)
- 石头堆总和的1/2容量的背包的最大重量和剩余重量差值
- 动态规划：目标和！(opens new window)
- 用数组中的数凑数目标target，求组合数
- 动态规划：一和零！(opens new window)
- 背包的容量增加了一个维度，求最大价值
- 动态规划：关于完全背包，你该了解这些！(opens new window)
- 每类物品的数量无限，状态转移时讨论有差异
- 动态规划：给你一些零钱，你要怎么凑？(opens new window)
- 只有三类物品，物品数量无限，凑出总金额，求组合数
- 动态规划：Carl称它为排列总和！(opens new window)
- 看似求组合实际求排列，完全背包中外层背包内层物品求排列，外层物品内层背包求组合
- 动态规划：以前我没得选，现在我选择再爬一次！(opens new window)
- 每次爬的楼层数不固定，求的是排列数
- 动态规划： 给我个机会，我再兑换一次零钱(opens new window)
- 不求组合数，求所需最少硬币个数
- 动态规划：一样的套路，再求一次完全平方数(opens new window)
- 使用完全平方和凑整数，求所需最少数量，和零钱兑换一模一样。注意遍历i，但使用i*i凑和
- 动态规划：单词拆分(opens new window)
- 用字符串列表填满单词，问能否刚好装满背包
- 动态规划：关于多重背包，你该了解这些！(opens new window)、
- 面试频率低
- 听说背包问题很难？ 这篇总结篇来拯救你了(opens new window)
打家劫舍系列
- 动态规划：开始打家劫舍！(opens new window)
- 每家偷还是不偷？状态转移时选择最优解
- 动态规划：继续打家劫舍！(opens new window)
- 房屋成环，则不要同时考虑首尾两家
- 动态规划：还要打家劫舍！(opens new window)
- 树形dp掌握树的遍历方式，因为要记录金额所以要后序遍历。将空节点状态推断为0，统一递推公式
股票系列
- 动态规划：买卖股票的最佳时机(opens new window)
- 买卖一次，每天是持有状态或者不持有状态
- 动态规划：买卖股票的最佳时机II(opens new window)
- 买卖多次
- 动态规划：买卖股票的最佳时机III(opens new window)
- 限定交易次数为2次，按照交易阶段划分状态
- 动态规划：买卖股票的最佳时机IV(opens new window)
- 限定交易次数为k次，仍按照交易阶段划分状态，不过发现奇数天和偶数天规律
- 动态规划：最佳买卖股票时机含冷冻期(opens new window)
- 有了冷冻期，状态划分更加详细
- 动态规划：买卖股票的最佳时机含手续费(opens new window)
- 无限次买卖，只需要再收获利润的时候减去手续费
- 动态规划：股票系列总结篇(opens new window)
子序列系列
- 动态规划：最长递增子序列(opens new window)
- 递增子序列长度增加要找到前一个递增子序列
- 动态规划：最长连续递增序列(opens new window)
- 前一个递增子序列只能是以 nums[i-1] 结尾
- 动态规划：最长重复子数组(opens new window)
- 重复子数组增加需要增加两个相同的元素。
- 动态规划：最长公共子序列(opens new window)
- 公共子序列增加也是需要增加 两个相同元素，但是中间可能插入其余元素
- 动态规划：不相交的线(opens new window)
- 与最长公共子序列相同
- 动态规划：最大子序和(opens new window)
- 连续子数组和的增加必须在后面增加一个元素
- 动态规划：判断子序列(opens new window)
- 动态规划：不同的子序列(opens new window)
- 动态规划：两个字符串的删除操作(opens new window)
- 动态规划：编辑距离(opens new window)
- 动态规划：回文子串(opens new window)
- 动态规划：最长回文子序列(opens new window)