动态规划使用场景
动态规划使用场景
动规的使用场景
求最值：最大值、最小值
可行性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]
背包问题的核心区别，第二维不是位置了，是一个值
跳跃游戏
- 问可行性
- 一维数组
- 有方向性
坐标型、可行性
要学更通用的算法，而不是只能解一题的算法（如贪心，贪心一般只能解一题）
不要追求贪心法，因为贪心真的不好想，会让人感觉你做过这个题
小结
动态规划的题必须是求最优值/可行性/方案数这三种情况之一
动态规划的状态依赖必须有方向性，不可以有循环依赖，（或者是与顺序无关时，那就是直接人为按照数组顺序即可）
坐标型动态规划的状态：坐标
坐标型动态规划的方程：上一步坐标
Unique Path II
方向性：状态间不能有循环依赖
当是上下左右都可以走时，会产生循环依赖，大概率不是dp
Knight shorest paths II
多向的只能用BFS
单向（左4个或者右4个）的可以用DP或BFS