动态规划分类：

  1. 线性dp
  2. 区间dp
  3. 背包dp
  4. 树形dp
  5. 状态压缩dp
  6. 数位dp
  7. 计数型dp
  8. 递推型dp
  9. 概率型dp
  10. 博弈型dp
  11. 记忆化搜索

动态规划思考方式：

1.线性dp

  • 线性 DP 问题是指递推方程具有明显的线性关系，有一维线性和二维线性。

  • 如：

  1. 三角形最小路径和
1
2
3
4
5
6
7
8
9
10
11
public int minimumTotal(List<List<Integer>> triangle) {
    int len = triangle.size();
    int[] dp = new int[len+1];
    for (int i = len-1; i >=0 ; i--) {
        for (int j = 0; j <=i ; j++) {
            int num = triangle.get(i).get(j);
            dp[j] = Math.min(dp[j],dp[j+1]) + num;
        }
    }
    return dp[0];
}
  1. 最长上升子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
public int lengthOfLIS(int[] nums) {
    int max = 0;
    int[] dp = new int[nums.length];
    for (int i = 0; i < nums.length; i++) {
        int count = 0;
        for (int j = 0; j <i ; j++) {
            if(nums[j] < nums[i] && dp[j] > count) count = dp[j];
        }
        dp[i] = count + 1;
        if(max < dp[i]) max = dp[i];
    }
    return max;
}
  1. 最长公共子序列
1
2
3
4
5
6
7
8
9
10
11
12
public int longestCommonSubsequence(String text1, String text2) {
    int n = text1.length();
    int m = text2.length();
    int[][] dp = new int[n+1][m+1];
    for (int i = 1; i <=n ; i++) {
        for (int j = 1; j <=m ; j++) {
            if(text1.charAt(i-1) == text2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] +1;
            else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
        }
    }
    return dp[n][m];
}

2.区间dp

  • 区间DP 问题是指递推方程具有明显的区间关系，有左端点和右端点。
  • 如：
  1. 最长回文子序列
1
2
3
4
5
6
7
8
9
10
11
12
13
public static int longestPalindromeSubseq(String s) {
    int len = s.length();
    char[] chars = s.toCharArray();
    int[][] dp = new int[len][len];
    for (int i = len-1; i >=0; i--) dp[i][i] = 1;    //base case
    for (int i = len-1; i >=0; i--) {
        for (int j = i+1; j <len ; j++) {
            if(chars[i] == chars[j]) dp[i][j] = dp[i+1][j-1]+2;
            else dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
        }
    }
    return dp[0][len-1];
}

3.背包dp

  • 背包DP 问题是指递推方程具有明显的限制条件
  • 在N中情况中 且满足某条件的 情况下 最优的选择情况
  • 如在背包重量不超过w的情况下，从N中物品中选择出 最有价值的物品 （01背包）
  • 详情参考 背包模板

4.树形dp

  • 在树的结构上求解问题，大部分可以直接用递归+记忆化解决
  • 如果有明显的递推关系，可以尝试使用递推+递归 直接消除子问题区间的重复计算 即树形dp
  • 如：
  1. 打家劫舍 III
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int rob(TreeNode root) {
    int[] res = dfs(root);
    return Math.max(res[0],res[1]);
}
//0 代表不偷，1 代表偷
public int[] dfs(TreeNode root) {
    if(root == null) return new int[]{0,0};
    int[] res = {0,0};
    int[] left = dfs(root.left);
    int[] right = dfs(root.right);
    res[0] = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
    res[1] = left[0] + right[0] + root.val;
    return res;
}

5.状压dp

1. 对于n个元素选与不选2种状态的问题（位运算）
  • 用2^n表示所有状态，第i位的状态 对应二进制数 第i位是0 还是1

2. 对于n个元素k种状态的问题（幂运算或累乘）
  • 1.如果每种物品选择的数量是相同的 m种状态，可用m^n表示所有状态

  • 2.如果每种物品的选择数量不同
    ： 无论如何都要让每一种状态与一个数字一一对应
  • 如：
  1. 526. 优美的排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int countArrangement(int N) {
    int dp[]=new int[1<<N];
    dp[0]=1;
    for(int i=0;i<dp.length;i++){
        int len=1;
        for(int j=0;j<N;j++)
            len+=i>>j&1;
        for(int j=1;j<=N;j++){
            if((i >> (j - 1) & 1)==0&& (j % len == 0 || len % j == 0)) {
                dp[i | (1 << j - 1)] += dp[i];   // 或运算，进行状态转移
            }
        }
    }
    return dp[(1<<N)-1];
}

6.数位 DP

  • 给定一个闭区间[l,r]，求这个区间中满足某种条件的数的总量

7.计数型 DP

  • 计数型DP都可以以组合数学的方法写出组合数，然后dp求组合数

  • 如：

62. 不同路径 I

1
2
3
4
5
6
7
8
9
10
public static int uniquePaths(int m, int n) {
    int[][] dp = new int[m+1][n+1];
    dp[1][1] = 1;
    for (int i = 1; i <=m ; i++) {
        for (int j = 1; j <=n ; j++) {
            dp[i][j] += dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m][n];
}

63. 不同路径 II

1
2
3
4
5
6
7
8
9
10
11
public int uniquePathsWithObstacles(int[][] grid) {
    int[][] dp = new int[grid.length+1][grid[0].length+1];
    if(grid[0][0] == 1) return 0;
    dp[1][1] = 1;
    for (int i = 1; i <=grid.length ; i++) {
        for (int j = 1; j <=grid[0].length ; j++) {
            if(grid[i-1][j-1] == 0) dp[i][j] += dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[grid.length][grid[0].length];
}

8.递推型 DP

  • 所有线性递推关系都可以用矩阵快速幂做，可以O(logN)，最典型是斐波那契数列

  • 如：

70. 爬楼梯

1
2
3
4
5
6
7
8
9
10
11
12
13
 public int climbStairs(int n) {
    int tmp = 0;
    int a = 1;
    int b = 2;
    if(n == 1) tmp = 1;
    if(n == 2) tmp = 2;    
    for(int i=3;i<=n;i++){
        tmp = a+b;
        a = b;
        b = tmp;     
    }
    return tmp;
}

9.概率型 DP

  • 给定一些的事件及其发生的概率问在某个条件下发生的概率 且这些事件之间有递推关系

  • 看似可以用dfs也能用dp，但要注意概率型问题都有一个精度边界

  • 如：

808. 分汤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public double soupServings(int N) {
    if(N>=4800) return 1.0;
    int n = (int) Math.ceil(N/25.0);
    double[][] dp = new double[n+1][n+1];
    dp[0][0] = 0.5;
    for (int i = 1; i <= n ; i++) {
        dp[i][0] = 0;
        dp[0][i] = 1;
    }
    for (int i = 1; i <= n; ++i){
        int a1 = i - 4 > 0 ? i - 4 : 0;//不足4，按4算（实际上是不足100，按100算，然后分配完了，没有剩余）
        int a2 = i - 3 > 0 ? i - 3 : 0;//不足3，按3算（实际上是不足75，按75算，然后分配完了，没有剩余）
        int a3 = i - 2 > 0 ? i - 2 : 0;//不足2，按2算（实际上是不足50，按75算，然后分配完了，没有剩余）
        int a4 = i - 1 > 0 ? i - 1 : 0;//不足1，按1算（实际上是不足25，按25算，然后分配完了，没有剩余）
        for(int j = 1; j <= n; ++j) {
            int b1 = j;
            int b2 = j - 1 > 0 ? j - 1 : 0;//不足1，按1算（实际上是不足25，按25算，然后分配完了，没有剩余）
            int b3 = j - 2 > 0 ? j - 2 : 0;//不足2，按2算（实际上是不足50，按75算，然后分配完了，没有剩余）
            int b4 = j - 3 > 0 ? j - 3 : 0;//不足3，按3算（实际上是不足75，按75算，然后分配完了，没有剩余）
            //状态转移方程：dp[i][j] = 0.25 * (dp[i-100][j] + dp[i-75][j-25] + dp[i-50][j-50] + dp[i-75][j-25])
            //将N缩小为原来的25分之一的转移方程：dp[i][j] = 0.25 * (dp[i-4][j] + dp[i-3][j-1] + dp[i-2][j-2] + dp[i-3][j-1])
            dp[i][j]= 0.25 * (dp[a1][b1] + dp[a2][b2] + dp[a3][b3] + dp[a4][b4]);
        }
    }
    return dp[n][n];
}

dfs解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static Map<String,Double> map;
public double soupServings(int N) {
    if(N>=4800) return 1;
    map = new HashMap<>();
    int n = (int) Math.ceil(N/25.0);
    return dfs(n,n);
}
public static double dfs(int i,int j){
    if(i<=0 && j<=0) return 0.5;
    else if(i<=0 && j>0) return 1;
    else if(i>0 && j<=0) return 0;
    else if(map.containsKey(i + " " + j)) return map.get(i + " " + j);
    else{
        double sum = 0.25*(dfs(i-4,j)+dfs(i-3,j-1)+
                dfs(i-2,j-2)+dfs(i-1,j-3));
        map.put(i + " " + j,sum);
        return sum;
    }
}

837. 新21点
反向递推

1
2
3
4
5
6
7
8
9
10
11
public double new21Game(int N, int K, int W) {
    double[] dp = new double[N+W+1];
    for (int i = K; i <=N ; i++) dp[i] = 1;
    double sum = 0;
    for (int i = 0; i <W ; i++) sum += dp[K+i];
    for (int i = K-1; i >=0 ; i--) {
        dp[i] = sum/W;
        sum += dp[i] - dp[i+W];
    }
    return dp[0];
}

后面待更新….