简介
什么是动态规划
动态规划，英文：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.买卖股票的最佳时机 II123.买卖股票的最佳时机 III188.买卖股票的最佳时机 IV309.最佳买卖股票时机含冷冻期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.不同路径 II96.不同的二叉搜索树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.出界的路径数
详见原文：
https://blog.csdn.net/pl0321/article/details/115507286