【九章算法强化班】动态规划

发表于 | 分类于 ， | 浏览 次
字数统计: 7,891 | 阅读时长 ≈ 40

outline

滚动数组

  • house robber I/II
  • Maximal Square

记忆化搜索

  • longest increasing subsequence
  • coins in a line

动态规划四要素

  1. 状态
  2. 转移方程
  3. 初始化
  4. 答案

滚动数组优化

f[i] = max(f[i-1],f[i-2]+A[i]);

转化为：

f[i%2] = max(f[(i-1)%2],f[(i-2)%2])

滚动数组优化不会对时间复杂度进行优化，而只是对空间进行优化

例题1. House Robber

给定一个数组，代表抢劫商店可以获得的价值，不可以抢劫相邻的商店，计算能够获得的最大价值

思路：

序列型dp

f[i]代表抢劫前i个商店能够获得的最大值

对于店铺i可以有抢和不抢两种情况：

  1. 如果抢，则不能抢f[i-1]，则前i个商店的最大值为前i-2个商店的最大值加上第i个商店的价值
  2. 如果不抢，则前i个商店的最大值=前i-1个商店的最大值

取两种情况的最大值

转移方程:f[i] = max(f[i-1],f[i-2]+nums[i])

代码：

public int rob(int[] nums) {
    if(nums.length == 0){
        return 0;
    }
    if(nums.length == 1){
        return nums[0];
    }
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0],nums[1]);
    for(int i = 2;i < nums.length;i++){
        dp[i] = Math.max(dp[i-1],dp[i-2] + nums[i]);
        System.out.println(dp[i]);
    }
    return dp[nums.length-1];
}

用滚动数组优化

转移方程：f[i] = max(f[i-1],f[i-2]+nums[i])

根据前面的分析，对于每一个商店i，我们只需要考虑商店i-1和i-2，也就是状态i只与它的前两个状态有关，所以我们只需要维护一个长度为2的数组来记录状态即可。

状态转移方程转化为f[i%2] = max(f[(i-1)%2],f[(i-2)%2]+nums[i])

代码：

public int rob(int[] nums) {
    if(nums.length == 0){
        return 0;
    }
    if(nums.length == 1){
        return nums[0];
    }
    int[] dp = new int[2];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0],nums[1]);
    for(int i = 2;i < nums.length;i++){
        dp[i%2] = Math.max(dp[(i-1)%2],dp[(i-2)%2] + nums[i]);
    }
    return dp[(nums.length-1)%2];
}

这道题是状态只与前两个状态有关，如果推广到一般，如果状态i与前k个状态有关，则有：

f[i%k] = max(f[(i-1)%k],f[(i-2)%k]+nums[i])

例题2. House Robber II

首尾商店算相邻的商店，也就是商店是一个环。

思路：

对于成环的问题有两个小技巧：

  1. 拆分数组的方式，将计算一个数组的问题转化成计算两个数组：
    1. 去掉最后一个元素
    2. 去掉第一个元素
  2. 将原数组copy一份，首尾相接，本题不适用

代码：

public int rob(int[] nums) {
    int len = nums.length;
    if(len == 0){
        return 0;
    }
    if(len == 1){
        return nums[0];
    }
    if(len == 2){
        return Math.max(nums[0],nums[1]);
    }
    
    int[] dp1 = new int [len-1];
    int[] dp2 = new int [len-1];
    dp1[0] = nums[0];
    dp1[1] = Math.max(nums[0],nums[1]);
    dp2[0] = nums[1];
    dp2[1] = Math.max(nums[1],nums[2]);
    for(int i = 2;i < len-1;i++){
        dp1[i] = Math.max(dp1[i-1],dp1[i-2] + nums[i]);
        dp2[i] = Math.max(dp2[i-1],dp2[i-2] + nums[i+1]);
    }
    return Math.max(dp1[nums.length-2],dp2[nums.length-2]);
}

滚动数组优化：

public int rob(int[] nums) {
    int len = nums.length;
    if(len == 0){
        return 0;
    }
    if(len == 1){
        return nums[0];
    }
    if(len == 2){
        return Math.max(nums[0],nums[1]);
    }
    
    int[] dp1 = new int [2];
    int[] dp2 = new int [2];
    dp1[0] = nums[0];
    dp1[1] = Math.max(nums[0],nums[1]);
    dp2[0] = nums[1];
    dp2[1] = Math.max(nums[1],nums[2]);
    for(int i = 2;i < len-1;i++){
        dp1[i%2] = Math.max(dp1[(i-1)%2],dp1[(i-2)%2] + nums[i]);
        dp2[i%2] = Math.max(dp2[(i-1)%2],dp2[(i-2)%2] + nums[i+1]);
    }
    return Math.max(dp1[(nums.length-2)%2],dp2[(nums.length-2)%2]);
}

例题3. Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

For example, given the following matrix:

> 1 0 1 0 0
> 1 0 1 1 1
> 1 1 1 1 1
> 1 0 0 1 0
>
>

>

Return 4.

找到全为1的正方形的最大面积

思路：

定位正方形，需要一个三维数组[x,y,a]

其中xy为正方形顶点坐标，a为边长

baseline：

x,y,a三层循环从0到n，然后x，y从1到a一共5层循环，复杂度

dp

对于一个点(i,j) (nums[i,j] = 1)，如要计算以其为右下角的最大正方形边长，需要考虑三个点：

  1. 以(i-1,j-1)为右下角的最大正方形边长
  2. 以(i,j-1)为最右点的矩形长度
  3. 以(i-1,j)为最下点的矩形长度

取三个值中最小的+1就是以(i,j)为右下角的矩形最大边长

因此：

  1. 状态：

    f[i][j]表示以以(i,j)为右下角的矩形最大边长

  2. 转移方程：

    if(matrix[i][j] == 1){
      f[i][j] = max(f[i-1],[j-1],up[i-1][j],left[i][j-1])+1
    }
    if(matrix[i][j] == 0){
      f[i][j] = 0;
    }

    改进：

    上面的方法除了维护f之外，还需要维护up和left数组，其实可以直接用f来代替up和left。

    if(matrix[i][j] == 1){
      f[i][j] = max(f[i-1],[j-1],f[i-1][j],f[i][j-1])+1
    }
    if(matrix[i][j] == 0){
      f[i][j] = 0;
    }

  3. 初始化

    f[i][0] = matrix[i][0]
    f[0][j] = matrix[0][j]

  4. 答案

    max(f[i][j])

代码：

class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSquare = 0;
        int rows = matrix.length;
        if (rows == 0){
            return 0;
        }
        int cols = matrix[0].length;
        int[][] dp = new int[matrix.length][matrix[0].length];
        //初始化
        for (int i = 0;i <rows;i++){
            if(matrix[i][0] == '1'){
                dp[i][0] = 1;
                maxSquare = 1;
            }
        }
        for (int j = 0;j <cols;j++) {
            if(matrix[0][j] == '1'){
                dp[0][j] = 1;
                maxSquare = 1;
            }
        }
        for(int i = 1;i < rows;i++){
            for(int j = 1;j < cols;j++) {
                if(matrix[i][j] == '1'){
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                    maxSquare = Math.max(maxSquare, dp[i][j]);
                }
                else{
                    dp[i][j] = 0;
                }
            }
        }
        return maxSquare*maxSquare;
    }
}

滚动数组优化：

对于每一个元素(i,j)，只与它前一行和前一列的元素有关，与其前两行的元素无关，因此可以对其行进行滚动数组优化

转移方程变为：

if(matrix[i][j] == 1){
  f[i%2][j] = max(f[(i-1)%2],[j-1],f[(i-1)%2][j],f[i%2][j-1])+1
}
if(matrix[i][j] == 0){
  f[i%2][j] = 0;
}

代码：

class Solution {
    public int maximalSquare(char[][] matrix) {
        int maxSquare = 0;
        int rows = matrix.length;
        if (rows == 0){
            return 0;
        }
        int cols = matrix[0].length;
        int[][] dp = new int[2][matrix[0].length];
        //初始化
        for (int j = 0;j <cols;j++) {
            if(matrix[0][j] == '1'){
                dp[0][j] = 1;
                maxSquare = 1;
            }
        }
        for(int i = 1;i < rows;i++){
            for(int j = 0;j < cols;j++) {
                //每行第一个元素
                if(j == 0){
                    if(matrix[i][j] == '1'){
                        dp[i%2][j] = 1;
                        maxSquare = Math.max(maxSquare, dp[i%2][j]);
                    }
                    else{
                        dp[i%2][j] = 0;
                    }
                    
                }
                else if(matrix[i][j] == '1'){
                    dp[i%2][j] = Math.min(dp[(i-1)%2][j-1],Math.min(dp[(i-1)%2][j],dp[i%2][j-1]))+1;
                    maxSquare = Math.max(maxSquare, dp[i%2][j]);
                }
                else{
                    dp[i%2][j] = 0;
                }
            }
        }
        return maxSquare*maxSquare;
    }
}

follow up：

01矩阵里面找一个，对角线全为1， 其他为0的正方形

转移方程：

if(matrix[i][j] == 1){
  f[i][j] = max(f[i-1],[j-1],up[i-1][j],left[i][j-1])+1
}
if(matrix[i][j] == 0){
  f[i][j] = 0;
}
其中up和left表示前面连续0的个数

二维动态规划空间优化（二维滚动数组）总结

这类题目特点：

f[i][j] = 由f[i-1]行 来决定状态， 第i行跟 i-1行之前毫无关系， 所以状态转变为：

f[i%2][j] = 由f[(i-1)%2]行来决定状态

还有一些题目可以用滚动数组进行优化：

习题1. Unique Paths

习题2. Minimum Path Sum

习题3. Edit Distance

记忆化搜索

  • 本质上是动态规划
  • 动态规划就是解决了重复计算的搜索
  • 动态规划的实现方式：
    • 循环（从小到大递推）
    • 记忆化搜索（从大到小）
      • 画搜索树
      • 滚动数组优化，万金油

例题1. Longest Increasing Subsequence

见【九章算法基础班】动态规划/)

例题2. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

> nums = [
>   [9,9,4],
>   [6,6,8],
>   [2,1,1]
> ]
>
>

>

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

> nums = [
>   [3,4,5],
>   [3,2,6],
>   [2,2,1]
> ]
>
>

>

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

分析：

用for循环解决这道题不知道起点在哪，即初始状态找不到

用搜索：

用搜索的方式，f[i][j] 为以点(i,j)为结尾的最长递增子序列长度，则需要看其上下左右四个点中没有被访问过的点，计算以这些点为结尾的最长递增子序列长度，这样就会有很多重复计算的点，因此可以用记忆化搜索，把计算过的点的信息存储下来，后面用到的时候直接查找即可。

记忆化搜索：

  • 状态： f[i][j] 为以点(i,j)为结尾的最长递增子序列长度
  • 转移方程：
    • a = +-1;b = 0;
    • b = +-1;a = 0;
    • f[i][j] =f[x+a][x+b]+1,if(a[x][y]>a[x+a][x+b])
  • 初始化
    • f[i][j] = 1
  • 答案
    • max f[i][j]

代码：

public class LongestIncreasingPathinaMatrix {
    //计算矩阵中ij点的最长递增子序列的长度
    public int search(int[][] matrix,int i,int j,int[][] dp){
        //如果已经计算过了
        if(dp[i][j] != 0){
            return dp[i][j];
        }
        int rows= matrix.length;
        int cols = matrix[0].length;
        int[] x_delta ={1,-1,0,0};
        int[] y_delta ={0,0,1,-1};
        int maxlen = 1;
        for(int k = 0; k < 4;k++){
            int x = i + x_delta[k];
            int y = j + y_delta[k];
            //如果上下左右的节点都没有越界,而且当前点的值大于其相邻点的值
            if(x >= 0 && x < rows && y >= 0 && y < cols && matrix[i][j] > matrix[x][y]){
                maxlen = Math.max(maxlen,search(matrix,x,y,dp)+1);
            }
        }
        dp[i][j] = maxlen;
        return dp[i][j];
    }
    public int longestIncreasingPath(int[][] matrix) {
        if(matrix.length == 0){
            return 0;
        }
        int[][] dp = new int[matrix.length][matrix[0].length];
//        //初始化每个点最长递增子序列长度为1
//        for(int i = 0;i < dp.length;i++){
//            for(int j = 0 ; j < dp[0].length;j++){
//                dp[i][j] = 1;
//            }
//        }
        int res = 1;
        for(int i = 0;i < dp.length;i++){
            for(int j = 0 ; j < dp[0].length;j++){
                res = Math.max(res,search(matrix,i,j,dp));
            }
        }
        return res;
    }
    public static void main(String[] args){
        LongestIncreasingPathinaMatrix test = new LongestIncreasingPathinaMatrix();
        int[][] matrix = {{9,9,4},{6,6,8},{2,1,1}};
        int res = test.longestIncreasingPath(matrix);
        System.out.print(res);
    }
}

总结：什么时候用记忆化搜索

  1. 状态转移特别麻烦，不是顺序性。
  2. 初始化状态不是很容易找到。
  3. 从大到小

博弈类DP

连两个人做游戏

解决博弈类DP通常用记忆化搜索的方法

例题1.coins in a line

There are n coins in a line. Two players take turns to take one or two coins from right side until there are no more coins left. The player who take the last coin wins.

Could you please decide the first play will win or lose?

Example

n = 1, return true.

n = 2, return true.

n = 3, return false.

n = 4, return true.

n = 5, return true.

两个人轮流选取硬币，每次只能选1个或者2个，取到最后一个石子的人获胜，给定石子数量，返回第一个选的人（先手）能否获胜。

分析：

画搜索树，以4个coin为例
先手层：			 4T
	   			1↙      ↘2
后手层：		3F	 	   2T
 			1↙   ↘2     1↙   ↘2
先手层：     2T     1T   1T      0F
  
搜索树中的TorF表示当前选择coin的选手的输赢
因为两个选手都会选择对自己最为有利的方式选取硬币，因此假设两个选手在开始的时候就已经绘制了这样的搜索树，以4枚硬币的情况为例，先手可以选择1个或者2个:
1. 选1个，还剩3个，此时后手无论选择1个还是2个，先手都可以赢
2. 选2个，还剩2个，此时后手选2个先手就会输掉比赛
所以先手选择对自己最为有利的方式，选择1个，赢得比赛。
由此可见，当前有n个coin的情况下， 该选手是否能够赢得比赛与在剩余n-1和n-2枚硬币的情况下对手是否能够赢得比赛有关。
以f(i)表示在剩余i枚硬币情况下当前选手是否能够获胜，
则当下层节点中至少有一个为false时，本层即可获胜
状态转移方程为: f(i) = !f(i-1)||!f(i-2)
初始化：f(1)=f(2)=true
答案：f(i)

代码：

public boolean firstWillWin(int n) {
    // write your code here
    boolean[] dp = new boolean[n];
    if(n==0){
        return false;
    }
    if(n <= 2){
        return true;
    }
    dp[0] = true;
    dp[1] = true;
    for(int i = 2;i < n;i++){
        dp[i] = !dp[i-1] || !dp[i-2];
    }
    return dp[n-1];
}

例题2. coins in a line II

There are n coins with different value in a line. Two players take turns to take one or two coins from left side until there are no more coins left. The player who take the coins with the most value wins.

Could you please decide the first player will win or lose?

Example

Given values array A = [1,2,2], return true.

Given A = [1,2,4], return false.

给定硬币序列，硬币具有价值，两个人轮流选取硬币，每次可以选1个或者2个获得相应的价值，最终获得价值多的人获胜，问先手能够获胜

分析：

f[i]:表示还剩i个硬币，当前取硬币的人最后最多取硬币的价值
如果f[i]>所有硬币价值的一半则可以获胜
以[5,1,2,10]为例
先手层：    	 [5,1,2,10]
		       1↙	    ↘2
后手层：     [1,2,10]     [2,10]
		   1↙	 ↘2     1↙   ↘2
先手层：  [2,10]   [10] [10]    []
两个人在选取硬币的时候，会选择给对方留下尽可能少的价值
转移方程为：f[i] = sum[i]- min(f[i-1],f[i-2])
初始化：
f[1] = coins[i-1]
f[2] = coins[i-1]+coins[i-2]
答案：
if dp[n] > sum[coins]/2

代码：

public boolean firstWillWin(int[] values) {
    // write your code here
    if(values.length <= 2){
        return true;
    }
    int[] sums = new int[values.length];
    int sum = 0;
    for(int i = values.length-1;i>=0;i--){
        sum += values[i];
        sums[i] = sum;
    }
    int[] dp = new int[values.length];
    dp[0] = sums[sums.length-1];
    dp[1] = sums[sums.length-2];
    for(int i = 2;i < values.length;i++){
        dp[i] = sums[values.length-i-1] - Math.min(dp[i-1],dp[i-2]);
    }
    return dp[values.length-1] > sums[0]/2;
}

例题3. Coins in a Line III

There are n coins in a line. Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

Could you please decide the first player will win or lose?

Example

Given array A = [3,2,2], return true.

Given array A = [1,2,4], return true.

Given array A = [1,20,4], return false.

和II一样coin带有价值，选取时可以从头部或者尾部选取一个coin。

分析：

初始：[3, 2, 2]
                  [3, 2, 2]
                   dp[0][2]
                /           \
        取左3  /              \ 取右2
             /                 \
         [2, 2]                [3, 2]
        dp[1][2]              dp[0][1]
          /    \                  /  \
   取左2 /       \ 取右2    取左3 /    \ 取右2
        /         \             /      \
    [2]            [2]        [2]      [3]
  dp[2][2]     dp[1][1]     dp[1][1]   dp[0][0]
 
这道题目属于区间型dp
dp[i][j] 现在还第i到第j的硬币，现在当前取硬币的人（先手）最后最多取硬币价值；这里是区间型DP，下标表示区间范围
转移方程：
sum[i][j]第i到第j的硬币价值总和
dp[i][j] = sum[i][j] - min(dp[i+1][j], dp[i][j-1]);
初始化：
dp[i][i] = coin[i]
答案：
dp[0][n-1] > sum[coins]/2

代码：

//记忆化搜索    
public int search(int[] values,int[][] sums,int[][] dp,int i,int j){
        if(dp[i][j] != 0){
            return dp[i][j];
        }
        dp[i][j] = sums[i][j] - Math.min(dp[i+1][j],dp[i][j-1]);
        return dp[i][j];
    }
    public boolean firstWillWin(int[] values) {
        int[][] sums = new int[values.length][values.length];
        int[][] dp = new int[values.length][values.length];
        //sums[i][j]为从i到j的coins价值和
        for(int i = 0; i < values.length;i++){
            sums[i][i] = values[i];
            dp[i][i] = values[i];
            int sum = sums[i][i];
            for(int j = i+1;j < values.length;j++){
                sum += values[j];
                sums[i][j] = sum;
            }
        }
        return search(values,sums,dp,0,values.length-1) > sums[0][values.length-1]/2;
    }

区间型DP

特点：

  1. 求一段区间的解max/min/count
  2. 转移方程通过区间更新
  3. 从大到小更新，用记忆化搜索

例题1. Stone Game

There is a stone game.At the beginning of the game the player picks n piles of stones in a line.

The goal is to merge the stones in one pile observing the following rules:

  1. At each step of the game, the player can merge two adjacent piles to a new pile.
  2. The score is the number of stones in the new pile.

You are to determine the minimum of the total score.

Example

For [4, 1, 1, 4], in the best solution, the total score is 18:

> 1. Merge second and third piles => [4, 2, 4], score +2
> 2. Merge the first two piles => [6, 4]，score +6
> 3. Merge the last two piles => [10], score +10
>
>

>

Other two examples:

[1, 1, 1, 1] return 8 [4, 4, 5, 9] return 43

给定数组，每次合并相邻元素直至全部合并，每次合并需要花费两个元素价值之和，返回最小的花费

分析：

以[3,4,5,6]为例：
死胡同:容易想到的一个思路从小往大，枚举第一次合并是在哪? 转而用记忆化搜索的思路，从大到小，先考虑最后的0 ~ n-1合并的总花费。
正确的打开方式：
将区间拆分，看成是两个区间的合并
                        [3,4,5,6]
                          (0,3)
               ↙		   ↓   			 ↘
      [3]+[4,5,6]	   [3,4]+[5,6]	   [3,4,5]+[6]   
      (0,0)+(1,3)	   (0,1)+(2,3)	   (0,2)+(3,3)
            ↙   ↘
   (1,1)+(2,3) (1,2)+(3,3) .....
  • State:
    • dp[i][j]表示把第i到第j个石子合并到一起的最小花费
  • Function:
    • 预处理sum[i,j]表示i到j所有石子价值和
    • dp[i][j] = min(dp[i][k]+dp[k+1][j]+sum[i,j]) 对于所有k属于{i,j}
  • Intialize:
    • for each i
      • dp[i][i] = 0
  • Answer:
    • dp[0][n-1]

代码：

public int search(int[] stones,int[][] dp,int i,int j){
    if(i > j){
        return 0;
    }
    if(dp[i][j]!= 0){
        return dp[i][j];
    }
    int minCost = Integer.MAX_VALUE;
    for(int idx = i;idx <= j;idx++){
        minCost = Math.min(minCost,Math.min(search(stones,dp,i,idx),search(stones,dp,idx+1,j)));
    }
    dp[i][j] = minCost;
    return dp[i][j];
}
public int StoneGame(int[] stones){
    int[][] dp = new int[stones.length][stones.length];
    //初始化
    for(int i = 0 ;i < stones.length;i++){
        dp[i][i] = stones[i];
    }
    return search(stones,dp,0,stones.length-1);
}

例题2. Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note:
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

>     nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
>    coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167
>

戳气球，每次戳破气球i可以获得价值nums[i-1]*nums[i]&nums[i+1]，返回可以获得的最大利润。

分析：

							[3, 1, 5, 8]
					↙		↙		↘		   ↘
最后一次打爆的气球:	3		  1			5 		     8
获得价值：                               1*5*1
				[1,5,8]   [3,5,8]    [3,1](5)[8]   [3,1,5]
								  ↙    ↘    ↓    
最后一次打爆的气球:		           3	   1   8
获得价值						1*3*5  1*1*5  5*8*1
						    (3)[1](5) [3](1)(5)
							    ↓         ↓ 
最后一次打爆的气球:		          1          3
获得价值				      3*1*5       1*3*1

  • State:

    • dp[i][j]表示把第i到第j个气球打爆获得的最大价值

  • Function:

    计算dp[i][j] 需要遍历ij区间内所有的点，看做最后一个从ij区间中删除的点，删除该点时获得的价值为nums[i-1]*nums[k]*nums[j+1]，然后再删除该点之前，其左边和右边的节点已经全部被删除，所以转移方程为：

    • dp[i][j] = max(nums[i-1]*nums[k]*nums[j+1] + dp[i][k-1] + dp[k+1][j]) 对于所有k属于{i,j}

  • Intialize:

    • for each i
      • dp[i][i] = 0

  • Answer:

    • dp[0][n-1]

代码：

class Solution {
    //计算戳破从i到j所有气球获得的coins
    public int solve(int[] nums,int[][] max,int i,int j){
        if(i > j){
            return 0;
        }
        //如果已经计算过了
        if(max[i][j] != 0){
            return max[i][j];
        }
        int maxVal = 0;
        //假设idx是ij区间中最后一个被戳破的气球
        for(int idx = i;idx <= j;idx++){
            int left = i-1 < 0?1:nums[i-1];
            int right = j+1 >= nums.length ?1:nums[j+1];
            int temp = left * right * nums[idx];
            maxVal = Math.max(maxVal,temp + solve(nums,max,i,idx-1) + solve(nums,max,idx+1,j));
        }
        max[i][j] = maxVal;
        return maxVal;
    }
    public int maxCoins(int[] nums) {
        int[][] max = new int[nums.length][nums.length];//打爆ij所有气球的最大值
        //Arrays.fill(max,-1);
        return solve(nums,max,0,nums.length-1);
    }
}

例题3. Scramble String

Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.

Below is one possible representation of s1 = "great":

>     great
>    /    \
>   gr    eat
>  / \    /  \
> g   r  e   at
>            / \
>           a   t
>
>

>

To scramble the string, we may choose any non-leaf node and swap its two children.

For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

>     rgeat
>    /    \
>   rg    eat
>  / \    /  \
> r   g  e   at
>            / \
>           a   t
>
>

>

We say that "rgeat" is a scrambled string of "great".

Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

>     rgtae
>    /    \
>   rg    tae
>  / \    /  \
> r   g  ta  e
>        / \
>       t   a
>
>

>

We say that "rgtae" is a scrambled string of "great".

Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1

分析：

对于s1和s2，找不同的分割点k，将其分别分为两个子数组。若s1的两个子数组和对应的s2的两个子数组都是scramble的，则s1和s2就是scramble的。例如，s1[0…i]被分为0…k，k+1…i，其对应的s2子数组为0…k，k+1…i或者0…i-k-1, i-k…i（即s2的前k个元素或者后k个元素对应于s1的前k个元素，比如s1=abc，s2=acb，第一层递归时比较的是s1左边的子数组和s2左边的子数组以及s1右边的子数组和s2右边的子数组，第二层递归比较右边两个子数组时，就要比较s1右边子数组的左边子数组”b”和s2右边子数组的右边子数组”b”），只要两种情况里面有一种满足，则s1和s2就是scramble的。

( isScramble(s2[0…k], s1[0…k]) && isScramble(s2[k+1…j], s1[k+1…i]) ) || ( isScramble(s2[0…k], s1[i-k…i]) && isScramble(s2[k+1…j], s1[0…i-k-1]) )，（k = 0,1,2 … i-1，k相当于字符串的分割点)

因此可以用记忆化搜索来保存子问题，设dp[i][j][k]表示s2从j开始长度为k的子串是否可以由s1从i开始长度为k的子串转换而成:

状态：

dp[i][j][k] 表示s1从第i个开始s2从第j个开始的k个字母是否是scramble string

因此状态转移方程为：

对于所有的i属于[1,k]:
s11 = s1.substring(0, i);  
s12 = s1.substring(i, i+k-1); 
s21 = s2.substring(0, i);  
s22 = s2.substring(i, i+k-1)
s23 = s2.substring(j, j+k-i-1);  
s24 = s2.substring(j+k-i, j+k-1); 
for i = x -> x+k ：
  dpx[k] = (dpx[i] && dpx+i[k-i]) || dpx[i] && dpx+i[k-i])

初始化：

dp[i][j][1] = s1[i]==s[j].

答案：

dp[0][0][len]

代码：

class Solution {
    public boolean search(boolean[][][] dp,boolean[][][] visited,int i,int j,int k){
        //如果计算过了，直接返回
        if(visited[i][j][k]){
            return dp[i][j][k];
        }
        dp[i][j][k] = false;
        for(int idx = 1;idx < k;idx++){
            if((search(dp,visited,i,j,idx) && search(dp,visited,i+idx,j+idx,k-idx) )||
                    (search(dp,visited,i,j+k-idx,idx) && search(dp,visited,i+idx,j,k-idx))){
                dp[i][j][k] = true;
                break;
            }
        }
        visited[i][j][k] = true;
        return dp[i][j][k];
    }
    public boolean isScramble(String s1, String s2) {
        if(s1.length() != s2.length()){
            return false;
        }
        int len = s1.length();
        boolean[][][] dp = new boolean[len][len][len+1];
        boolean[][][] visited = new boolean[len][len][len+1];
        //初始化
        for(int i = 0;i < len;i++){
            for(int j = 0;j < len;j++){
                dp[i][j][1] = s1.charAt(i)== s2.charAt(j);
                visited[i][j][1] = true;
            }
        }
        return search(dp,visited,0,0,len);
    }
}

递归也可以做

class Solution {
    public boolean isScramble(String s1, String s2) {
        if(s1.equals(s2)) {
            return true;
        }
        
        int[] count = new int[26];
        for(int i = 0;i < s1.length();i++) {
            count[s1.charAt(i) - 'a']++;
            count[s2.charAt(i) - 'a']--;
        }
        for(int i = 0;i < count.length;i++) {
            if(count[i] != 0) {
                return false;
            }
        }
        
        for(int i = 1;i < s1.length();i++) {
            if(isScramble(s1.substring(0, i), s2.substring(0, i)) 
               && isScramble(s1.substring(i), s2.substring(i))) {
                return true;
            }
            if(isScramble(s1.substring(0, i), s2.substring(s2.length()-i)) 
               && isScramble(s1.substring(i), s2.substring(0, s2.length()-i))) {
                return true;
            }
        }
        return false;
    }
}

背包类DP

特点：

  1. 用值作为DP维度
  2. DP过程就是填写矩阵
  3. 可以用滚动数组优化

例题1. Backpack

Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?

Example

If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5], so that the max size we can fill this backpack is 10. If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.

You function should return the max size we can fill in the given backpack.

给定背包容量和物品数组，返回最大的

分析：

不可以用贪心，比如[8,7,5]，容量为12

如果用贪心法放了8就放不下其他的了，但是放7和5得到的总容量更大，所以不能用贪心法。

以items = [2,3,4,5]，size=11为例分析：
定以一个矩阵，行数为items.length，列数为size
idx 0	1	2	3	4	5	6	7	...
 0	T	F	F	F	F	F	F	F	...
 1	T	F	T	F	F	F	F	F	...
 2	T	F	T	T	F	T	F	F	...
 3	T	...
 4	T	...
state:
f[i][S]表示在前i个物品中取出一些能否组成和为S
function：
在前i个物品中是否有选择方式使得取出的物品和为S，可以分两种情况讨论：
1. 选择第i个物品：需要考虑在前i-1和物品中是否可以选取一些物品组成s-a[i]
2. 不选第i个物品：需要考虑在前i-1和物品中是否可以选取一些物品组成s
因此状态转移方程为:
f[i][S] = f[i-1][s-a[i]] or f[i-1][s]
initial:
f[i][0] = true;
f[0][j] = false;j!=0
answer:
max j,f[i][j] = true;
滚动数组优化：
可以看出来f[i][S]只与前一行有关，所以可以进行二位滚动数组优化

代码：

public int backPack(int m, int[] A) {
    // write your code here
    boolean[][] dp = new boolean[A.length+1][m+1];
    int res = 0;
    //初始化
    for(int i = 0; i < A.length+1;i++){
        dp[i][0] = true;
    }
    for(int i = 1; i < m+1;i++){
        dp[0][i] = false;
    }
    for(int i = 1;i < m+1;i++){
        for(int j = 1;j < A.length+1;j++){
            if(i-A[j-1] < 0){
                dp[j][i] = dp[j-1][i];
            }
            else{
                dp[j][i] = dp[j-1][i-A[j-1]] || dp[j-1][i];
            }
            if(dp[j][i]){
                res =i;
            }
        }
    }
    return res;
}

例题2. BackPack马甲变换1，硬币凑整

给定面值1,2,5,10的硬币无穷多个，请问能够凑成80元的方案总数。

分析：

states：
dp[i][j]表示用前i种硬币凑成j元钱的方案总数
以[1,2,5,10] total = 80 为例：
依然采用填写矩阵的方式
idx	0	1	2	3	4	5	6	7	8	9	10	...
0	1	0	0	0	0	0	0	0	0	0	0	...
1	1	1	1	1	1	1	1	1	1	1	1	...
2	1	1	2	2	3	3	...
3	1	...
4	1
动态转移方程：
用前i种硬币凑成j元，考虑第i种硬币取的个数k
dp[i][j] = dp[i-1][j-val[i]] +....+dp[i-1][j-val[i]*k]
初始化：
dp[i][0] = 1;
dp[0][j] = 0;(j!=0)
答案：
dp[val.length][total]

代码：

public int backPack(int m, int[] A) {
    int[][] dp = new int[A.length+1][m+1];
    //初始化
    for(int i = 0;i < A.length+1;i++){
        dp[i][0] = 1;
    }
    for(int i = 1;i < m+1;i++){
        dp[0][i] = 0;
    }
    for(int i = 1;i < A.length+1;i++){
        for(int j = 1;j < m+1;j++){
            int k = 0;
            while(k * A[i-1] <= m){
                dp[i][j] += dp[i-1][j-k*A[i-1]];
                k++;
            }
        }
    }
    return dp[A.length][m];
}

例题3. Coin Change

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

给定硬币面值，和总价值，返回能凑成总价值所用硬币数的最小值

思路：

和上一题思路类似

state:

dp[i][j] 表示用i种硬币凑成j元所需要的最少硬币数量

function：

dp[i][j] = min{dp[i-1][j-k*A[i-1]]+k}
for each k*A[i-1]] <= amout && dp[i-1][j-k*A[i-1]] != 0

initial：

dp[i][0] = 1;
dp[0][j] = 0;(j!=0)

answer：

dp[coins.length][amount]

代码：

public int coinChange(int[] coins, int amount) {
        if(amount == 0){
            return 0;
        }
        int[][] dp = new int[coins.length+1][amount+1];
        //初始化
        for(int i = 0;i <coins.length+1;i++){
            for(int j = 0;j < amount+1;j++){
                if(j == 0){
                    dp[i][0] = 0;
                }
                else{
                    dp[i][j] = -1;
                }
            }
        }
        for(int i = 1;i < coins.length+1;i++){
            for(int j = 1;j < amount+1;j++){
                int k = 0;
                int minCount = Integer.MAX_VALUE;
                while(k * coins[i-1] <= j){
                    if(dp[i-1][j-k*coins[i-1]] != -1){
                        minCount = Math.min(minCount,dp[i-1][j-k*coins[i-1]]+k);
                    }
                    k++;
                }
                if(minCount != Integer.MAX_VALUE){
                    dp[i][j] = minCount;
                }
            }
        }
        if(dp[coins.length][amount] == 0){
            return -1;
        }
        else{
            return dp[coins.length][amount];
        }

优化：

例题4. BackPack 马甲变换2

把一个数组[1,24,5,6]尽量平分

可以转化为背包问题：

数组总和为36，一半为18

背包容量为18，用数组中的数字尽量将背包装满

Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

  1. Each of the array element will not exceed 100.
  2. The array size will not exceed 200.

Example 1:

> Input: [1, 5, 11, 5]
>
> Output: true
>
> Explanation: The array can be partitioned as [1, 5, 5] and [11].
>
>

>

Example 2:

> Input: [1, 2, 3, 5]
>
> Output: false
>
> Explanation: The array cannot be partitioned into equal sum subsets.
>

返回是否能够取到整个数组的一半。

public class PartitionEqualSubsetSum {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for(int i = 0; i < nums.length;i++){
            sum += nums[i];
        }
        if(sum%2 != 0){
            return false;
        }
        sum = sum/2;
        boolean[][] dp = new boolean[nums.length+1][sum+1];
        //chushihua
        for(int i = 0;i < nums.length+1;i++){
            dp[i][0] = true;
        }
        for(int i = 1; i < nums.length+1;i++){
            for(int j = 1;j < sum+1;j++){
                if(j < nums[i-1]){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[nums.length][sum];
    }
}

例题5. Backpack II

给定物品占空间和物品价值数组，背包容量，如何装能够使得背物品价值最高

不可以用贪心算法

分析：

依然采用补全矩阵的方法
体积数组为A，价值数组为val,容量为S
state：
f[i][j]表示在前i个物品中选取一些物品，构成总体积为j，所获得的最高价值是多少
function：
考虑第i个物品，有选和不选两种情况：
1. 选：总价值为f[i-1][j-A[i-1]] + val[i-1]
2. 不选：总价值为f[i-1][j]
取两者之中较大的，因此状态转移方程为：
f[i][j] = max(f[i-1][j],f[i-1][j-A[i-1]] + val[i-1])
initial:
f[0][i] = 0
f[i][0] = 0
answer：
f[A.length][S]

代码：

public int backPackII(int m, int[] A, int[] V) {
    // write your code here
    int[][] dp = new int[A.length+1][m+1];
    for(int i = 1;i < A.length+1;i++){
        for(int j = 0;j < m+1;j++){
            if(j >= A[i-1]){
                dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-A[i-1]]+V[i-1]);
            }
            else{
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[A.length][m];
}

例题6. K Sum

给定数组A=[1,2,3,4],k=2,target=5

在A中选2个元素，和为5，返回方案个数

思路：

state:
f[i][j][k]表示在前i个元素中选取j个出来和为t个方案个数
function:
考虑第i个元素，有选和不选两种方案，两种方案数求和
f[i][j][k] = f[i-1][j-1][t-A[i-1]] + f[i-1][j][t]
initial:
f[i][0][0] = 1;
answer:
f[A.length][k][target]

代码：

public class Solution {
    /**
     * @param A: An integer array
     * @param k: A positive integer (k <= length(A))
     * @param target: An integer
     * @return: An integer
     */
    public int kSum(int[] A, int k, int target) {
        // write your code here
        int[][][] dp = new int[A.length+1][k+1][target+1];
        //Chushihua
        for(int i = 0; i < A.length+1;i++){
            dp[i][0][0] = 1;
        }
        for(int i = 1;i < A.length+1;i++){
            for (int j = 1;j < k+1;j++){
                for(int l = 0;l < target+1;l++){
                    if(l >= A[i-1]){
                        dp[i][j][l] = dp[i-1][j][l] + dp[i-1][j-1][l-A[i-1]];
                    }
                    else{
                        dp[i][j][l] = dp[i-1][j][l];
                    }
                }
            }
        }
        return dp[A.length][k][target];
    }
}

优化：

例题7. Minnimum Adjus

总结

  • 区间类DP
    • 从大到小去思考，将区间划分成小区间
    • 主要通过记忆化搜索来解决
  • 背包类DP
    • 用值座位DP维度
    • 用for循环填写矩阵数值
    • 可以用滚动数组做优化