动态规划模板
动态规划分类:
- 线性dp
- 区间dp
- 背包dp
- 树形dp
- 状态压缩dp
- 数位dp
- 计数型dp
- 递推型dp
- 概率型dp
- 博弈型dp
- 记忆化搜索
动态规划思考方式:
1.线性dp
线性 DP 问题是指递推方程具有明显的线性关系,有一维线性和二维线性。
如:
plaintext
1 | public int minimumTotal(List<List<Integer>> triangle) { |
plaintext
1 | public int lengthOfLIS(int[] nums) { |
plaintext
1 | public int longestCommonSubsequence(String text1, String text2) { |
2.区间dp
- 区间DP 问题是指递推方程具有明显的区间关系,有左端点和右端点。
- 如:
plaintext
1 | public static int longestPalindromeSubseq(String s) { |
3.背包dp
- 背包DP 问题是指递推方程具有明显的限制条件
- 在N中情况中 且满足某条件的 情况下 最优的选择情况
- 如在背包重量不超过w的情况下,从N中物品中选择出 最有价值的物品 (01背包)
- 详情参考 背包模板
4.树形dp
- 在树的结构上求解问题,大部分可以直接用递归+记忆化解决
- 如果有明显的递推关系,可以尝试使用递推+递归 直接消除子问题区间的重复计算 即树形dp
- 如:
plaintext
1 | public int rob(TreeNode root) { |
5.状压dp
1. 对于n个元素选与不选2种状态的问题(位运算)
- 用2^n表示所有状态,第i位的状态 对应二进制数 第i位是0 还是1
2. 对于n个元素k种状态的问题(幂运算或累乘)
- 1.如果每种物品选择的数量是相同的 m种状态,可用m^n表示所有状态
- 2.如果每种物品的选择数量不同
: 无论如何都要让每一种状态与一个数字一一对应
- 如:
plaintext
1 | public int countArrangement(int N) { |
6.数位 DP
- 给定一个闭区间[l,r],求这个区间中满足某种条件的数的总量
7.计数型 DP
计数型DP都可以以组合数学的方法写出组合数,然后dp求组合数
如:
plaintext
1 | public static int uniquePaths(int m, int n) { |
plaintext
1 | public int uniquePathsWithObstacles(int[][] grid) { |
8.递推型 DP
所有线性递推关系都可以用矩阵快速幂做,可以O(logN),最典型是斐波那契数列
如:
plaintext
1 | public int climbStairs(int n) { |
9.概率型 DP
给定一些的事件及其发生的概率问在某个条件下发生的概率 且这些事件之间有递推关系
看似可以用dfs也能用dp,但要注意概率型问题都有一个精度边界
- 如:
plaintext
1 | public double soupServings(int N) { |
dfs解法
plaintext
1 | static Map<String,Double> map; |
837. 新21点
反向递推
plaintext
1 | public double new21Game(int N, int K, int W) { |
后面待更新….
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Kid1999' Blog!