leetcode算法之动态规划总结（11种DP类型，70道全部搞懂）——总结非常全面
简介
什么是动态规划
动态规划，英文：Dynamic Programming，简称DP，将问题分解为互相重叠的子问题，通过反复求解子问题来解决原问题就是动态规划，如果某一问题有很多重叠子问题，使用动态规划来解是比较有效的。
求解动态规划的核心问题是穷举，但是这类问题穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下。动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出**正确的「状态转移方程」**才能正确地穷举。重叠子问题、最优子结构、状态转移方程就是动态规划三要素
动态规划和其他算法的区别
- 动态规划和分治的区别：动态规划和分治都有最优子结构 ，但是分治的子问题不重叠
- 动态规划和贪心的区别：动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优解，所以它永远是局部最优，但是全局的解不一定是最优的。
- 动态规划和递归的区别：递归和回溯可能存在非常多的重复计算，动态规划可以用递归加记忆化的方式减少不必要的重复计算
动态规划的解题方法
- 递归+记忆化(自顶向下)
- 动态规划（自底向上）
下面通过例子由浅至深详细讲解。
所有例题均来自leetcode，所示代码均通过所有测试。
参考文章，将所有的DP问题分成11大类，本文将每一类的题目进行补充，并对这些题目的解法进行探讨。
题目
1、线性 DP
- 最经典单串：
300.最长上升子序列 中等 - 其他单串
32.最长有效括号 困难
376.摆动序列
368.最大整除子集
410.分割数组的最大值 - 最经典双串：
1143.最长公共子序列 中等 - 其他双串
97.交错字符串 中等
115.不同的子序列 困难
583.两个字符串的删除操作 - 经典问题：
53.最大子序和 简单
120.三角形最小路径和 中等
152.乘积最大子数组 中等
354.俄罗斯套娃信封问题
887.鸡蛋掉落（DP+二分） 困难 - 打家劫舍系列: (打家劫舍3 是树形DP)
198.打家劫舍 中等
213.打家劫舍 II 中等 - 股票系列:
121.买卖股票的最佳时机
122.买卖股票的最佳时机 II
123.买卖股票的最佳时机 III
188.买卖股票的最佳时机 IV
309.最佳买卖股票时机含冷冻期
714.买卖股票的最佳时机含手续费 - 字符串匹配系列
72.编辑距离 困难
44.通配符匹配 困难
10.正则表达式匹配 困难 - 其他
375.猜数字大小 II
2、区间 DP
5.最长回文子串 中等
516.最长回文子序列
87. 扰乱字符串 困难
312.戳气球 困难
730.统计不同回文子字符串
1039.多边形三角剖分的最低得分
664.奇怪的打印机
1246. 删除回文子数组
3、背包 DP
377. 组合总和 Ⅳ416.分割等和子集 (01背包-要求恰好取到背包容量)
494.目标和 (01背包-求方案数)
322.零钱兑换 (完全背包)
518.零钱兑换 II (完全背包-求方案数)
474.一和零 (二维费用背包)
4、树形 DP
124.二叉树中的最大路径和 困难
1245.树的直径 (邻接表上的树形DP)
543.二叉树的直径 简单
333.最大 BST 子树
337.打家劫舍 III 中等
5、状态压缩 DP
464.我能赢吗
526.优美的排列
935.骑士拨号器
1349.参加考试的最大学生数
6、数位 DP
233.数字 1 的个数 困难
902.最大为 N 的数字组合
1015.可被 K 整除的最小整数
7、计数型 DP
计数型DP都可以以组合数学的方法写出组合数，然后dp求组合数
62.不同路径63.不同路径 II
96.不同的二叉搜索树
1259.不相交的握手 (卢卡斯定理求大组合数模质数)
8、递推型 DP
70.爬楼梯509.斐波那契数
576. 出界的路径数
688. “马”在棋盘上的概率
935.骑士拨号器
957.N 天后的牢房
1137.第 N 个泰波那契数
9、概率型 DP
求概率，求数学期望
808.分汤
837.新21点
10、博弈型 DP
策梅洛定理，SG 定理，minimax
- 翻转游戏
293.翻转游戏
294.翻转游戏 II - Nim游戏
292.Nim 游戏 - 石子游戏
877.石子游戏
1140.石子游戏 II - 井字游戏
348.判定井字棋胜负
794.有效的井字游戏
1275.找出井字棋的获胜者
11、记忆化搜索
本质是 dfs + 记忆化，用在状态的转移方向不确定的情况
329.矩阵中的最长递增路径
576.出界的路径数