Table of Contents

动态规划五部曲

五部曲

• 确定dp数组

• 确定递推公式

• 初始化

• 遍历顺序

• 举例推导

动态规划系列基础问题

• 关于动态规划，你该了解这些！

理解动态规划五部曲，利用打印dp数组进行debug。理解是用动态规划问题的一些特点。比如总最优问题能拆出多个最优子问题，各个父子问题之间有递推关系，伴随着状态的转移。

• 理解动态规划五部曲，利用打印dp数组进行debug。理解是用动态规划问题的一些特点。比如总最优问题能拆出多个最优子问题，各个父子问题之间有递推关系，伴随着状态的转移。

• 动态规划：斐波那契数

非常自然的能理解父子问题的存在以及之间的递推关系。

• 非常自然的能理解父子问题的存在以及之间的递推关系。

• 动态规划：爬楼梯

每次选择爬一步还是两步意味着两种状态，动态规划优化了这个一步步决策的过程，前一爬和后一爬之间有着状态的转移。

• 每次选择爬一步还是两步意味着两种状态，动态规划优化了这个一步步决策的过程，前一爬和后一爬之间有着状态的转移。

• 动态规划：使用最小花费爬楼梯

逻辑和上面相同，在选择的时候考虑爬一步花费最少还是爬两步花费最少

• 逻辑和上面相同，在选择的时候考虑爬一步花费最少还是爬两步花费最少

• 动态规划：不同路径

考虑到达当前位置能有几种选择。

• 考虑到达当前位置能有几种选择。

• 动态规划：不同路径还不够，要有障碍！

障碍物位置的状态为 0

• 障碍物位置的状态为 0

• 动态规划：整数拆分，你要怎么拆？

拆分成2个数以及可以继续拆分的数，两种情况。

• 拆分成2个数以及可以继续拆分的数，两种情况。

• 动态规划：不同的二叉搜索树

先确定根节点，根据根节点进行分类讨论状态

• 先确定根节点，根据根节点进行分类讨论状态

背包问题系列

• 动态规划：关于01背包问题，你该了解这些！

理解01背包由暴力回溯转化而来。背包容量、物品、重量、价值几个概念

• 理解01背包由暴力回溯转化而来。背包容量、物品、重量、价值几个概念

• 动态规划：关于01背包问题，你该了解这些！（滚动数组）

背包应当逆序防止被覆盖

• 背包应当逆序防止被覆盖

• 动态规划：分割等和子集可以用01背包！

能否把容量为 sum / 2的背包装满。

• 能否把容量为 sum / 2的背包装满。

• 动态规划：最后一块石头的重量 II

石头堆总和的1/2容量的背包的最大重量和剩余重量差值

• 石头堆总和的1/2容量的背包的最大重量和剩余重量差值

• 动态规划：目标和！

用数组中的数凑数目标target，求组合数

• 用数组中的数凑数目标target，求组合数

• 动态规划：一和零！

背包的容量增加了一个维度，求最大价值

• 背包的容量增加了一个维度，求最大价值

• 动态规划：关于完全背包，你该了解这些！

每类物品的数量无限，状态转移时讨论有差异

• 每类物品的数量无限，状态转移时讨论有差异

• 动态规划：给你一些零钱，你要怎么凑？

只有三类物品，物品数量无限，凑出总金额，求组合数

• 只有三类物品，物品数量无限，凑出总金额，求组合数

• 动态规划：Carl称它为排列总和！

看似求组合实际求排列，完全背包中外层背包内层物品求排列，外层物品内层背包求组合

• 看似求组合实际求排列，完全背包中外层背包内层物品求排列，外层物品内层背包求组合

• 动态规划：以前我没得选，现在我选择再爬一次！

每次爬的楼层数不固定，求的是排列数

• 每次爬的楼层数不固定，求的是排列数

• 动态规划： 给我个机会，我再兑换一次零钱

不求组合数，求所需最少硬币个数

• 不求组合数，求所需最少硬币个数

• 动态规划：一样的套路，再求一次完全平方数

使用完全平方和凑整数，求所需最少数量，和零钱兑换一模一样。注意遍历i，但使用i*i凑和

• 使用完全平方和凑整数，求所需最少数量，和零钱兑换一模一样。注意遍历i，但使用i*i凑和

• 动态规划：单词拆分

用字符串列表填满单词，问能否刚好装满背包

• 用字符串列表填满单词，问能否刚好装满背包

• 动态规划：关于多重背包，你该了解这些！、

面试频率低

• 面试频率低

• 听说背包问题很难？ 这篇总结篇来拯救你了

打家劫舍系列

• 动态规划：开始打家劫舍！

每家偷还是不偷？状态转移时选择最优解

• 每家偷还是不偷？状态转移时选择最优解

• 动态规划：继续打家劫舍！

房屋成环，则不要同时考虑首尾两家

• 房屋成环，则不要同时考虑首尾两家

• 动态规划：还要打家劫舍！

树形dp掌握树的遍历方式，因为要记录金额所以要后序遍历。将空节点状态推断为0，统一递推公式

• 树形dp掌握树的遍历方式，因为要记录金额所以要后序遍历。将空节点状态推断为0，统一递推公式

股票系列

• 动态规划：买卖股票的最佳时机

买卖一次，每天是持有状态或者不持有状态

• 买卖一次，每天是持有状态或者不持有状态

• 动态规划：买卖股票的最佳时机II

买卖多次

• 买卖多次

• 动态规划：买卖股票的最佳时机III

限定交易次数为2次，按照交易阶段划分状态

• 限定交易次数为2次，按照交易阶段划分状态

• 动态规划：买卖股票的最佳时机IV

限定交易次数为k次，仍按照交易阶段划分状态，不过发现奇数天和偶数天规律

• 限定交易次数为k次，仍按照交易阶段划分状态，不过发现奇数天和偶数天规律

• 动态规划：最佳买卖股票时机含冷冻期

有了冷冻期，状态划分更加详细

• 有了冷冻期，状态划分更加详细

• 动态规划：买卖股票的最佳时机含手续费

无限次买卖，只需要再收获利润的时候减去手续费

• 无限次买卖，只需要再收获利润的时候减去手续费

• 动态规划：股票系列总结篇

子序列系列

• 动态规划：最长递增子序列

递增子序列长度增加要找到前一个递增子序列

• 递增子序列长度增加要找到前一个递增子序列

• 动态规划：最长连续递增序列

前一个递增子序列只能是以 nums[i-1] 结尾

• 前一个递增子序列只能是以 nums[i-1] 结尾

• 动态规划：最长重复子数组

重复子数组增加需要增加两个相同的元素。

• 重复子数组增加需要增加两个相同的元素。

• 动态规划：最长公共子序列

公共子序列增加也是需要增加 两个相同元素，但是中间可能插入其余元素

• 公共子序列增加也是需要增加 两个相同元素，但是中间可能插入其余元素

• 动态规划：不相交的线

与最长公共子序列相同

• 与最长公共子序列相同

• 动态规划：最大子序和

连续子数组和的增加必须在后面增加一个元素

• 连续子数组和的增加必须在后面增加一个元素

• 动态规划：判断子序列

• 动态规划：不同的子序列

• 动态规划：两个字符串的删除操作

• 动态规划：编辑距离

• 动态规划：回文子串

• 动态规划：最长回文子序列