使用场景

动规的使用场景

求最值：最大值、最小值

可行性80-90%：是否存在一种方案

方案总数：只求总数不求具体方案

前三种考的最多

状态压缩：用01进行压缩

动态规划的题型分类有什么？

不同题型的动态规划对一个的状态表示方法是不同的

如果成功的找对了题型，就能够解决DP最难的状态表示问题

DP最难的就是状态的设计，不同类型的DP的状态是有固定模式的

坐标型动态规划

dp[i] 表示从起点到坐标i的最优值/方案数/可行性

dp[i]j] 表示从起点到坐标i.j的最优值/方案数/可行性

代表题: Triangle, Unique Paths

前缀型动态规划

划分型

dp[i] 表示前i个字符的最优值/方案数/可行性

dp[i][j] 表示前i个字符划分为j个部分的最值/方案数/可行性

代表题: Word Break, Word Break Ill

二维的时候，有指定的信息，如确定要划分成多少个部分

匹配型

dp[i][j] 表示第一个字符串的前i个字符匹配上第二个字符串的前j个字符的最优值/方案数/可行性

代表题: Longest Common Subsequence, Wildcard Matching

坐标型和前缀型的重要区别：

坐标型：到这个位置

前缀型：这个及以前的这一段

区间型动态规划

dp[i][j] 表示区间i~j的最优值/方案数/可行性

代表题: Stone Game, Burst Balloons

子数组或子串上的区间

大区间依赖于小区间的结果

背包型动态规划

dp[i][j] 表示前i个物品里选出一些物品组成和为j的大小的最优值/方案数/可行性

代表题: Backpack 系列

如果限制物品的数量，可以拓展为3位dp[i][j][k]

背包问题的核心区别，第二维不是位置了，是一个值

跳跃游戏

1. 问可行性
2. 一维数组
3. 有方向性

坐标型、可行性

要学更通用的算法，而不是只能解一题的算法（如贪心，贪心一般只能解一题）

不要追求贪心法，因为贪心真的不好想，会让人感觉你做过这个题

小结

动态规划的题必须是求最优值/可行性/方案数这三种情况之一

动态规划的状态依赖必须有方向性，不可以有循环依赖，（或者是与顺序无关时，那就是直接人为按照数组顺序即可）

坐标型动态规划的状态：坐标

坐标型动态规划的方程：上一步坐标

Unique Path II

方向性：状态间不能有循环依赖

当是上下左右都可以走时，会产生循环依赖，大概率不是dp

Knight shorest paths II

多向的只能用BFS

单向（左4个或者右4个）的可以用DP或BFS