leetcode递归与动态规划

发表于

0-1背包

有一个容量为 N 的背包，要用这个背包装下物品的价值最大，这些物品有两个属性：体积 w 和价值 v。每件物品仅使用一次。

主要特点：每个物品只有一件，选择放或者不放。

f(i,v)表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：f(i,v)=max{f(i-1,v),f(i-1,v-c[i])+w[i]}。

放第i件物品：f(i,v) = 第i件物品的价值+i-1件物品放入v-第i件物品的花费

不放第i件物品：就是前i-1件物品放入容量为v的背包中。

416. 分割等和子集

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

完全背包

每件物品使用次数不限制。

多重背包

每个物品可选的次数不同。

汉诺塔

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
     * 汉诺塔问题
     * 递归方法来解决。
     * from  to   help
     * 一开始from有n个元素，需要将这n个元素移动到to中。可以分为三个步骤：
     *  1.将n-1个元素从from移动到help
     *  2.将第n个元素从from直接移到to
     *  3.将n-1个元素从help移动到to
     * */
public void hanuo(int N,String from,String to,String help){
    if(N==1){
        System.out.println("move 1 "+" form "+from+" to "+to);
    }else{
        hanuo(N-1,from,help,to);
        System.out.println("move "+N+" from "+from+" to "+to);
        hanuo(N-1,help,to,from);
    }
}

198.打家劫舍

1
2
3
4
5
6
7
8
9
10
11
12
13
//dp[i]到第i家可以偷多少钱dp[i]=max(dp[i-1],dp[i-2]+nums[i-1])
public int rob(int[] nums) {
    if(nums.length<1){
        return 0;
    }
    int[] dp = new int[nums.length+1];
    dp[0] = 0;
    dp[1] = nums[0];
    for(int i=2;i<=nums.length;i++){
        dp[i] = Math.max(dp[i-2]+nums[i-1],dp[i-1]);
    }
    return dp[nums.length];
}

打印字符串子序列

例如abc，打印a , ab , abc ,ac, bc,以及空字符串

1
2
3
4
5
6
7
8
9
public void printAllSub(char[] arr,int i,String res){
    if(i==arr.length){
        System.out.println(res);
        return ;
    }
    //存在两种情况，打印该元素以及不打印该元素
    printAllSub(arr,i+1,res);
    printAllSub(arr,i+1,res+String.valueOf(arr[i]));
}

生牛

1576899784912

64. 最小路径和

暴力递归解法

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
27
28
29
30
31
32
public int minPathSum(int[][] grid) {
    if(grid.length==0||grid[0].length==0){
        return 0;
    }
    return helperMinPath(grid,0,0);
}

/**
     * 递归来解决
     *  该方法表示从(row,col)走到右下角的距离
     *  1.到达最右下角节点，直接返回结果
     *  2.res  = min(向右走，向下走)
     * */
public int helperMinPath(int[][] grid,int row,int col){
    int val = grid[row][col];
    //走到最右下角点
    if(row==(grid.length-1)&&col == grid[0].length-1){
        return grid[row][col];
    }
    //走到最后一行或者是最后一列
    if(row==grid.length-1){
        return val+helperMinPath(grid,row,col+1);
    }
    if(col == grid[0].length-1){
        return val+helperMinPath(grid,row+1,col);
    }

    //取向下走以及往右走的最小值
    int down = helperMinPath(grid,row+1,col);
    int right = helperMinPath(grid,row,col+1);
    return Math.min(down,right)+val;
}

实际上，暴力递归有许多计算是重复的，这样造成时间复杂度过高，暴力嘀咕可以转化为动态规划。

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
27
28
29
30
31
32
public int minPathSum(int[][] grid) {
    if(grid.length==0||grid[0].length==0){
        return 0;
    }
    return DPMinPath(grid);
}

public int minPathSum(int[][] grid) {
    return DPMinpath(grid);
}
public int DPMinpath(int[][] matrix){
    if(matrix.length==0||matrix[0].length==0){
        return 0;
    }
    int m = matrix.length;
    int n = matrix[0].length;
    int[][] dp = new int[m][n];
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            if(i==0&&j==0){
                dp[i][j] =  matrix[i][j];
            }else if(i==0){
                dp[i][j] = dp[i][j-1]+matrix[i][j];
            }else if(j==0){
                dp[i][j] = dp[i-1][j]+matrix[i][j];
            }else{
                dp[i][j] = Math.min(dp[i-1][j]+matrix[i][j],dp[i][j-1]+matrix[i][j]);
            }
        }
    }
    return dp[m-1][n-1];
}

使用一维数组

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 int minPathSum(int[][] grid) {
        return DPMinpath(grid);
    }
    public int DPMinpath(int[][] matrix){
        if(matrix.length==0||matrix[0].length==0){
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[] dp = new int[n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(i==0&&j==0){
                    dp[0] =  matrix[i][j];
                }else if(i==0){
                    dp[j] = dp[j-1]+matrix[i][j];
                }else if(j==0){
                    dp[j] = dp[j]+matrix[i][j];
                }else{
                    dp[j] = Math.min(dp[j]+matrix[i][j],dp[j-1]+matrix[i][j]);
                }
            }
        }
        return dp[n-1];
    }
}

任意个数字相加等于aim?

1576925330206

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**第一种是递归方法来解决。每个元素有选择以及不选择两种可能
     * 假如i==arr.length，说明已经走完了最后一个元素，判断sum是否等于aim
     * 对于每一个元素，我们有选择加他或者不加他两种可能
     * @param arr1：输入的数组
     * @param i：数组中第几个数据
     * @param sum
     * @param aim：目标和
     * @return
     */
public  boolean process1(int[] arr1,int i,int sum,int aim){
    if(i==arr1.length){
        return sum==aim;
    }
    //分为选择该元素以及不选择该元素两种可能
    return process1(arr1,i+1,sum,aim)||process1(arr1,i+1,sum+arr1[i],aim);
}

/**
     * DP版本
     * 两个可变参数：sum以及i(元素个数)
     * */

public  boolean process1(int[] arr1,int aim){
    //计算sum范围
    int sum = 0;
    for(int ele:arr1){
        sum+=ele;
    }
    boolean[][] dp = new boolean[arr1.length+1][sum+1];
    /**
         * if(i==arr1.length){
         *    return sum==aim;
         *  }
         *  计算特殊情况
         * */
    for(int i=0;i<=sum;i++){
        dp[arr1.length][i] = i==aim?true:false;
    }
    for(int i=1;i<arr1.length;i++){
        for(int j=0;j<=sum;j++){
            dp[i][j] = dp[i+1][j]||dp[i+1][j+arr1[j]];
        }
    }
    return dp[0][0];
}

53. 最大子序和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

/**
     * 集合组成是以i个元素结尾的字段，比如[2,1,-1,4]有四个，分别是以2，1，-1，4结尾的子段
     * f(i) = max(f(i-1),0)+nums[i]，f(i)表示以i作为结尾的子段的所有元素之和
     * */
public int maxSubArray(int[] nums) {
    if(nums.length==1){
        return nums[0];
    }
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    int max = dp[0];
    for(int i=1;i<nums.length;i++){
        dp[i] = Math.max(dp[i-1],0)+nums[i];
        max = Math.max(max,dp[i]);
    }
    return max;
}

120. 三角形最小路径和

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
27
28
29
30
/**
     * 特殊情况：col = 0 dp[i][0] = dp[i-1][0]+triangle.get(i).get(0);
     *           每个list中的最后一个元素
     * dp[i][j] = min(dp[i-1][j],dp[i-1][j-1])+当前值
     * */
public int minimumTotal(List<List<Integer>> triangle) {
    if(triangle==null||triangle.size()==0){
        return 0;
    }
    int[][] dp = new int[triangle.size()][triangle.size()];
    dp[0][0] = triangle.get(0).get(0);
    for(int i=1;i<triangle.size();i++){
        dp[i][0] = dp[i-1][0]+triangle.get(i).get(0);
    }
    for(int i=1;i<triangle.size();i++){
        List<Integer> data = triangle.get(i);
        dp[i][data.size()-1] = dp[i-1][data.size()-2]+data.get(data.size()-1);
    }
    for(int i=1;i<triangle.size();i++){
        List<Integer> data = triangle.get(i);
        for(int j=1;j<data.size()-1;j++){
            dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j])+data.get(j);
        }
    }
    int min = Integer.MAX_VALUE;
    for(int i=0;i<triangle.get(triangle.size()-1).size();i++){
        min = Math.min(min,dp[triangle.size()-1][i]);
    }
    return min;
}

换钱方法数

1578623250591

递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
     * 假设[5,10,25,1]，targrt = 15
     * 使用0张5元的，剩下的15元在[10,25,1]中凑得。使用1张5元的，剩下的10元在[10,25,1]中凑得。使用两张5元的，剩下的5元在[10,25,1]中凑得。使用3张5元的，剩下0元，不用凑了。
     * 对[10,25,1]继续递归这个过程，直到遍历完这个数组。
     * */
public int coinChange(int[] coins, int target) {
    return helper(coins,0,target);
}

public int helper(int[] coins,int index,int amount){
    int res = 0;
    //遍历完数组，假如还剩下0元，那么这是一种选择方法
    if(index==coins.length){
        return amount==0?1:0;
    }
    for(int i=0;coins[index]*i<=amount;i++){
        res+=helper(coins,index+1,amount-coins[index]*i);
    }
    return res;
}

动态规划版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
     * 使用动态规划来完成，两个变量，index，amount，我们需要求的值是index=0，amount=target
     * 特殊情况：index==coins.length,amount==0?1:0
     * 普通情况：dp[i][j] = dp[index+1][amount-coins[index]]+dp[index+1][amount-coins[index]*2]....
     * */

public int coinChange2(int[] coins, int target) {
    //定义动态规划数组，index以及amount两个变量
    int[][] dp = new int[coins.length+1][target+1];
    dp[coins.length][0] = 1;
    for(int i=1;i<=target;i++) {
        dp[coins.length][i] = 0;
    }
    for(int i=coins.length-1;i>=0;i--){
        for(int j=0;j<=target;j++){
            //                for(int k=0;j-coins[i]*k>=0;k++) {
            //                    dp[i][j] += dp[i + 1][j - coins[i]*k];
            //                }
            dp[i][j] = dp[i+1][j]+(j-coins[i]>=0?dp[i][j-coins[i]]:0);
        }
    }
    return dp[0][target];
}

486.纸牌博弈问题

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
/**
     * 暴力递归
     * f(i,j):绝顶聪明的人在arr[i...j]上先拿纸牌，可以获得什么分数
     * s(i,j):绝顶聪明的人在arr[i...j]上后拿纸牌，可以获得什么分数
     * 返回玩家1先拿纸牌的分数以及玩家2后拿纸牌的分数
     * */
public boolean PredictTheWinner(int[] nums) {
    return first(nums,0,nums.length-1)>second(nums,0,nums.length-1);
}

/**
     * 先拿纸牌获取的分数
     * start==end:return nums[start]
     * strat!=end:可以取nums[start]或者是nums[end]，
     *      取nums[start]，那么，在[start+1,end]中后取
     *      取nums[end]，那么，在[start,end-1]中后取
     *      因为他绝顶聪明，所以会选取两个最大值取
     * */
public int first(int[] nums,int start ,int end){
    if(start==end){
        return nums[start];
    }
    return Math.max(nums[start]+second(nums,start+1,end),nums[end]+second(nums,start,end-1));
}

/**
     * 后拿纸牌获取的分数
     * start==end:直接返回0
     * strat!=end:对手可以取nums[start]或者是nums[end]，
     *      对手取nums[start]，那么，玩家就可以在[start+1,end]中先取
     *      对手取nums[end]，那么，玩家就可以在[start,end-1]中先取
     *      因为对手也是绝顶聪明，所以会留取最差的情况给玩家，返回最小值
     * */
public int second(int[] nums,int start ,int end){
    if(start==end){
        return 0;
    }
    return Math.min(first(nums,start+1,end),first(nums,start,end-1));
}


/**
     * 递归改动态规划
     * 需要准备两个动态规划数组，f以及s
     * 两个变量：start，end
     * */

public boolean PredictTheWinner(int[] nums) {
    if(nums.length<=1){
        return true;
    }
    int[][] f = new int[nums.length][nums.length];
    int[][] s = new int[nums.length][nums.length];
    for(int i=0;i<nums.length;i++){
        f[i][i] = nums[i];
    }
    for(int i=nums.length-2;i>=0;i--){
        for(int j=i+1;j<nums.length;j++){
            if(i!=j){
                f[i][j] = Math.max(nums[i]+s[i+1][j],nums[j]+s[i][j-1]);
                s[i][j] = Math.min(f[i+1][j],f[i][j-1]);
            }
        }
    }
    return f[0][nums.length-1]>=s[0][nums.length-1];
}

机器人达到指定位置

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
/**
     * 机器人到达指定位置方法数
     * N:N个位置
     * M:机器人开始的位置
     * K:需要走的步数
     * P:最终来到的位置
     * */
public int walkWay(int N,int M,int K,int P){
    if(N<2||M<1||K<1||P<1||M>N||P>N){
        return 0;
    }
    return walk(N,M,K,P);
}

/**
     * @param cur:当前所处的位置
     * @param rest：剩余的步数
     *
     */
public int walk(int N,int cur,int rest,int P){
    //步数走完了，看是否停在了P
    if(rest==0){
        return cur==P?1:0;
    }
    //假如走到了1位置，那么只能向右走
    if(cur==1){
        return walk(N,2,rest-1,P);
    }
    //假如走到了N位置，那么只能向左走
    if(cur==N){
        return walk(N,N-1,rest-1,P);
    }
    //其他位置，可以向左走向右走
    return walk(N,cur+1,rest-1,P)+walk(N,cur-1,rest-1,P);
}
/**
     * 递归转动态规划
     * 可变参数：cur，rest
     * 返回：dp[M][K]
     * */
public int walkWay2(int N,int M,int K,int P){
    if(N<2||M<1||K<1||P<1||M>N||P>N){
        return 0;
    }
    //K:rest N:cur
    int[][] dp = new int[K+1][N+1];
    dp[0][P] = 1;
    //因为rest==0时是初始的特殊情况，所以，所有值都应该根据rest==0时求得，所以应该rest值先进性遍历，即<=k
    for(int i =1;i<=K;i++){
        for(int j=1;j<=N;j++){
            if(j==1){
                dp[i][j] = dp[i-1][2];
            }else if(j==N){
                dp[i][j] = dp[i-1][N-1];
            }else{
                dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1];
            }
        }
    }
    return dp[K][M];
}