动态规划-背包

字数统计: 5.2k字   |   阅读时长: 24分

背包问题

图片

图片

0-1背包(物品只有一件)

二维数组

  1. dp[i][j] 容量为j的背包从[0, i]选物品，背包的最大价值
  2. 背包中放物品i dp[i][j] = dp[i-1][j-weights[i]] + values[i]
    背包中不放物品i(j<weights[i]时肯定放不下，还可能能放下物品i，但是物品i的价值不高，浪费了背包重量，不如用这些重量放其他的物品) dp[i][j] = dp[i-1][j]

dp[i][j] = max(dp[i-1][j-weights[i]] + values[i], dp[i-1][j])

  1. 初始化: dp[:][0] 为 0 dp[0][j] 对于j<weights[0]的j，dp[0][j]都为0，对于j>=weights[0]的j，都为values[0]
  2. 遍历方向 双重循环，外层循环遍历物品，内层循环遍历重量，对于每个物品，背包容量逐渐升高，计算最大价值
  3. 背包最大重量4
    图片
j=0 j=1 j=2 j=3 j=4
i=0 0 15 15 15 15
i=1 0 15 15 20 35
i=2 0 15 15 20 35

一维滚动数组

观察上述二维数组发现，dp[i][j]当前值，只与上一行的值有关，所以可以使用一维数组，只保存上一次的计算结果

  1. dp[j]容量为j的背包物品的最大价值
  2. dp[j] = max(dp[j], dp[j-weights[i]] + values[i])
    解释比较的两项 dp[j]：不放物品i，放物品[0, i-1]最大价值

dp[j-weights[i]] + values[i]：放物品i

  1. dp[0] 肯定为0 如果物品价值非负 其他都初始化为0
  2. 遍历方向 双重循环，外层循环遍历物品，内层循环遍历重量，但是遍历重量时要从大到小遍历，因为递推公式中dp[j-weights[i]] + values[i]，dp[j-weights[i]]是剩余的重量，该重量的最大价值由[0,i-1]物品决定，是上一次遍历到物品i-1时保存的结果，如果从小到大遍历，那么dp[0]至dp[j-1]上一层的结果都被覆盖了
  3. 例子同上
    j=4 j=3 j=2 j=1 j=0

i= 0 15 15 15 15 0

i= 1 35 20 15 15 0

i= 2 35 20 15 15 0

0-1背包问题的变体

dp[j]不是容量为j的背包物品最大价值，而是能装满容量为j的背包的方案数量

分割等和子集-最大价值

https://leetcode.cn/problems/partition-equal-subset-sum/

1
2
3
4
5
6
7
8
9
10
11
12
13
转为背包问题，背包容量 sum/2 物品的重量就是元素值 物品的价值也是元素值 
找到元素和为sum/2，就是背包刚好装满，就是价值刚好是sum/2，重量也是sum/2，说明就是刚好装满了
1. dp[j] 容量为j的背包最大价值
2. 放物品i 不放物品i
dp[j] = Math.max(dp[j], dp[j-nums[i]] + nums[i])
3. 没有负价值，都为0即可
4. 物品从前向后遍历，容量从大到小
5. [1,5,11,5]
    j=0    j=1    j=2    j=3    j=4    j=5    j=6    j=7    j=8    j=9    j=10    j=11
i=0  0      1      1      1      1      1      1      1      1      1      1       1
i=1  0      1      1      1      1      5      6      6      6      6      6       6
i=2  0      1      1      1      1      5      6      6      6      6      6       11
i=3  0      1      1      1      1      5      6      6      6      6      10       11
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int value : nums) {
        sum += value;
    }
    // 和是奇数不可能分割成相等的两部分
    if (sum % 2 == 1) {
        return false;
    }
    int bagWeight = sum / 2;
    int[] dp = new int[bagWeight+1];
    for (int value : nums) {
        for (int j=bagWeight; j>=value; j--) {
            dp[j] = Math.max(dp[j], dp[j-value] + value);
        }
    }
    return dp[bagWeight] == bagWeight;

}

目标和-满背包组合数

https://leetcode.cn/problems/target-sum/

  • 回溯也能解决
    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
    /*
        left - right = target
    即  left - (sum - left) = target
    即  left = (target + sum) / 2  如果 target + sum是奇数，
    (target + sum) / 2是小数，
    不存在这样的left组合
    用回溯法解决问题，组合总和问题
    */
    private int result = 0;
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int value : nums) {
            sum += value;
        }
        if ((sum + target) % 2 == 1) {
            return 0;
        }
        this.backtrack(nums, 0, (sum + target) / 2);
        return this.result;
    }
    // 回溯函数参数 搜索数组 开始的索引 目标和
    private void backtrack(int[] nums, int startIndex, int target) {
        // 递归终止
        if (target < 0) {
            return;
        }
        // 记录结果，注意元素中有0元素，所以在target为0时，不能剪枝返回，
        // 当递归到更深层时，如果为0，相加仍然满足目标和，如果返回会丢解
        if (target == 0) {
            this.result++;
        }

        for (int i=startIndex; i<nums.length; i++) {
            backtrack(nums, i+1, target-nums[i]);
        }
    }
  • 01背包动态规划
    1
    2
    3
    4
    5
    6
    7
    8
    9
        left - right = target
    即  left - (sum - left) = target
    即  left = (target + sum) / 2  如果 target + sum是奇数，(target + sum) / 2是小数，不存在这样的left组合
    转成01背包问题，把每个元素装到容量为(target + sum) / 2 的背包中
    1. dp[j] 装满容量为j的背包的方法
    2. dp[j] += dp[j - nums[i]] 累加所有元素的结果
    3. dp[0] = 1 装满容量为0的背包，方法有一种，就是什么都不放
    4. 外层循环遍历元素，内层循环倒序遍历容量
    5. [1, 1, 1, 1, 1] 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int findTargetSumWays(int[] nums, int target) {
    int sum = 0;
    for (int i=0; i<nums.length; i++) {
        sum += nums[i];
    }
    // 如果sum+target为奇数，(sum+target) / 2为小数，不可能凑出来
    if ((sum + target) % 2 == 1) {
        return 0;
    }
    // sum + target < 0时初始化会出错，所以需要单独处理，此时也凑不出来，因为元素非负
    if (sum + target < 0) {
        return 0;
    }
    
    int bagWeight = (sum + target) / 2;
    int[] dp = new int[bagWeight+1];
    dp[0] = 1;
    for (int value : nums) {
        for (int j=bagWeight; j>=value; j--) {
            dp[j] += dp[j-value];
        }
    }
    return dp[bagWeight];
}

最后一块石头的重量Ⅱ-最大价值

https://leetcode.cn/problems/last-stone-weight-ii/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
转为0-1背包问题，背包容量 sum/2，使该背包价值最大，剩余部分的石头重量，
与背包中的石头重量相互抵消，剩余的就是最小的重量
1. dp[j]容量为j的背包最大价值，价值就是重量
2. dp[j] = Math.max(dp[j], dp[j-stones[i]]+stones[i])
3. dp[0] = 0
4. 石头只能用一次 0-1背包问题，倒叙遍历背包
   求价值，先遍历物品，再遍历背包
5. [2,7,4,1,8,1] sum = 23 sum/2 = 11
    0   1   2   3   4   5   6   7   8   9   10  11
i=0  0   0   2   2   2   2   2   2   2   2   2   2
i=1  0   0   2   2   2   2   2   7   7   9   9   9
i=2  0   0   2   2   4   4   6   7   7   9   9   11
i=3  0   1   2   3   4   5   6   7   8   9   10  11
i=4  0   1   2   3   4   5   6   7   8   9   10  11
每个背包都达到最大价值，不用遍历了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int lastStoneWeightII(int[] stones) {
    int sum = 0;
    for (int stone : stones) {
        sum += stone;
    }
    int bagWeight = sum / 2;
    int[] dp = new int[bagWeight + 1];
    for (int stone : stones) {
        for (int j=bagWeight; j>=stone; j--) {
            dp[j] = Math.max(dp[j], dp[j-stone] + stone);
        }
    }
    // 剩余石头的重量 - 背包内的重量 向下取整，剩余石头的重量肯定大
    return sum - dp[bagWeight] - dp[bagWeight];
}

一和零-最大价值二维背包

https://leetcode.cn/problems/ones-and-zeroes/

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
0-1背包问题，不过是二维背包，背包的价值就是物品个数，每个物品价值都为1，让价值最大
1. dp[i][j] 能装m个0n个1的背包，能放物品的最大个数
2. 还是放当前物品或者不放当前物品两种情况，取这两种情况中的最大值
dp[i][j] = Math.max(dp[i][j], dp[i-zeroNum][j-oneNum]+1);
3. dp[0][0]为0，非零下标，没有物品可装时，数量为0
4. 0-1背包，容积倒序遍历，二维背包，先遍历容积的哪个维度都没关系
5. ["10", "0001", "111001", "1", "0"], m = 5, n = 3
第一个物品
    n=0    n=1    n=2    n=3
m=0  0      0      0      0
m=1  0      1      1      1
m=2  0      1      1      1
m=3  0      1      1      1
m=4  0      1      1      1      
m=5  0      1      1      1

第二个物品
    n=0    n=1    n=2    n=3
m=0  0      0      0      0
m=1  0      1      1      1
m=2  0      1      1      1
m=3  0      1      1      1
m=4  0      1      1      1      
m=5  0      1      2      2

第三个物品
    n=0    n=1    n=2    n=3
m=0  0      0      0      0
m=1  0      1      1      1
m=2  0      1      1      1
m=3  0      1      1      1
m=4  0      1      1      1      
m=5  0      1      2      2

第四个物品
    n=0    n=1    n=2    n=3
m=0  0      1      1      1
m=1  0      1      2      2
m=2  0      1      2      2
m=3  0      1      2      2
m=4  0      1      2      2      
m=5  0      1      2      3

第五个物品
    n=0    n=1    n=2    n=3
m=0  0      1      1      1
m=1  1      2      2      2
m=2  1      2      3      3
m=3  1      2      3      3
m=4  1      2      3      3      
m=5  1      2      3      3
dp[5][3] = 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int findMaxForm(String[] strs, int m, int n) {
    int[][] dp = new int[m+1][n+1];
    for (String str : strs) {
        int zeroNum = 0, oneNum = 0;
        for (char c : str.toCharArray()) {
            if (c == '0') {
                zeroNum++;
            } else {
                oneNum++;
            }
        }

        for (int i=m; i>=zeroNum; i--) {
            for (int j=n; j>=oneNum; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i-zeroNum][j-oneNum] + 1);
            }
        }
    }
    return dp[m][n];
}

完全背包(物品有无数件)

0-1背包问题，需要倒叙遍历背包容量

完全背包问题，需要正序遍历背包容量

组合数问题，先遍历物品

物品只会按给出的顺序排列，在计算dp[j] += dp[j-value]时dp[j-value]的数量只被value之前的元素填满

  排列数问题，先遍历背包容量

物品会按任意顺序排列，在计算dp[j] += dp[j-value]时，dp[j-value]的数量包含value之后满足条件的元素 [1, 2, 5]

dp[8] = dp[7] + dp[6] + dp[3]

dp[7]： 以1结尾，dp[7]肯定包含2+5与5+2

在计算dp[7]的时候 dp[7] = dp[6] + dp5 + dp2

所以dp[7]中肯定有2+5与5+2

dp[6]: 以2结尾，dp[6]肯定包含1+5与5+1，证明过程同上

dp[3]: 以5结尾，dp[3]肯定包含1+2与2+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
public int jumpFloorII(int target) {
    /*
        可以把n个台阶当成背包，每次跳的台阶当成物品
        可以重复跳某个数列的台阶，也就是物品可以重复，完全背包
        求的是装满背包的方式，而不是物品的价值
        所以并不是用价值的递推公式 dp[j] = max(dp[j], dp[j-weights[i]]+values[i])
        而是用组合数或排列数的递推公式 dp[j] += dp[j-nums[i]] (i=0, 1, 2...)
        1. dp[j] 跳到j台阶的方法
        2. dp[j] += dp[j-nums[i]] (i=0, 1, 2...)
        3. dp[0] = 1
        4. 先跳1个台阶，再跳2个台阶 与 先跳2个台阶，再跳1个台阶 是不一样的方式，所以是求排列数
        先遍历背包 再遍历物品
        5. [1, 2, 3, 4]  n=4
            j=0    j=1    j=2    j=3    j=4
     初始化   1      0      0      0      0
       i=1    1     0+1    0+1    0+2    0+4
       i=2    1      1     1+1    2+1    4+2
       i=3    1      1      2     3+1    6+1
       i=4    1      1      2      4     7+1
    */
    int[] dp = new int[target+1];
    dp[0] = 1;
    for (int j=1; j<=target; j++) {
        // i<=j 物品不能超过背包容量，不然装不进去
        for (int i=1; i<=j; i++) {
            dp[j] += dp[j-i];
        }
    }
    return dp[target];
}

组合总和Ⅳ

https://leetcode.cn/problems/combination-sum-iv/

1
2
3
4
5
target 背包容量，整数是物品
完全背包问题 排列数问题
递推公式 dp[j] += dp[j-nums[i]]
dp[0] = 1
先背包再物品，正序遍历
1
2
3
4
5
6
7
8
9
10
11
12
public int combinationSum4(int[] nums, int target) {
    int[] dp = new int[target+1];
    dp[0] = 1;
    for (int j=1; j<=target; j++) {
        for (int i=0; i<nums.length; i++) {
            if (nums[i] <= j) {
                dp[j] += dp[j-nums[i]];
            }
        }
    }
    return dp[target];
}
  • 也可以回溯，不过会超时
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    private int result;
    public int combinationSum4(int[] nums, int target) {
        this.backtrack(nums, target);
        return this.result;
    }

    private void backtrack(int[] nums, int target) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            // 不需要记录路径，只需要计数
            this.result++;
            return;
        }
        
        for (int i=0; i<nums.length; i++) {
            backtrack(nums, target-nums[i]);
        }
    }

零钱兑换Ⅱ

https://leetcode.cn/problems/coin-change-2/

1
2
3
4
5
6
不限制硬币数量，完全背包
满背包问题，求组合数

递推公式 dp[j] += dp[j-coins[i]]
dp[0] = 1，dp[非0] = 0
先物品再背包
1
2
3
4
5
6
7
8
9
10
public int change(int amount, int[] coins) {
    int[] dp = new int[amount+1];
    dp[0] = 1;
    for (int coin : coins) {
        for (int j=coin; j<=amount; j++) {
            dp[j] += dp[j-coin];
        }
    }
    return dp[amount];
}

零钱兑换

https://leetcode.cn/problems/coin-change/

1
2
3
4
5
硬币数量不限，完全背包
凑成总金额，满背包问题，最少数量
dp[j] = Math.min(dp[j], dp[j-coins[i]]+1)
dp[0] = 0 dp[非0] = MAX_VALUE
不是求组合与排列数，而是硬币数量，相当于价值，先遍历哪个都行
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount+1];
    for (int i=1; i<=amount; i++) {
        dp[i] = Integer.MAX_VALUE;
    }
    for (int coin : coins) {
        for (int j=coin; j<=amount; j++) {
                // dp[j-coin] 是最大值时不能+1，会溢出
                // 当dp[j-coin]是最大值的话，dp[j]不会变得更小，
                // 不用更新，直接跳过
            if (dp[j-coin] != Integer.MAX_VALUE) {
                dp[j] = Math.min(dp[j], dp[j-coin]+1);
            }
        }
    }
    return dp[amount]==Integer.MAX_VALUE ? -1 : dp[amount];
}

完全平方和

https://leetcode.cn/problems/perfect-squares/

1
2
3
4
5
完全背包 满背包最少数量
dp[j] = Math.min(dp[j], dp[j-nums[i]]+1)
dp[0] = 0 dp[非0] = MAX_VALUE
完全背包，正序遍历，求的时最少数量，先遍历哪个都行
dp 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int numSquares(int n) {
    int[] dp = new int[n+1];
    for (int i=1; i<=n; i++) {
        dp[i] = Integer.MAX_VALUE;
    }
    // 物品是平方数，最大不能超过背包容量
    for (int i=1; i*i<=n; i++) {
        // 始终记得，物品是平方数i*i
        for (int j=i*i; j<=n; j++) {
            if (dp[j-i*i] != Integer.MAX_VALUE) {
                dp[j] = Math.min(dp[j], dp[j-i*i]+1);
            }
        }
    }
    return dp[n];
}

单词拆分

https://leetcode.cn/problems/word-break/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    完全背包问题 满背包问题，但是不同于组合排列数与最小数量
    是能否使用单词装满背包，教程中说先遍历哪个都行
    但是我觉得只能先遍历背包
    如果先遍历物品，那么由物品组成字符串，只能按单词出现的顺序排列，
    即对于 s = "leetcodeleet", wordDict = ["leet", "code"] 按照单词出现顺序只能组成
    "leetleetcode"，无法在出现code后再出现leet

    1. dp[j] 长度为j的字符串，是否能由给出的单词构成
    2. dp[j] = dp[i] && [i, j)单词在字典中 
    3. dp[0] = true dp[非0] = false
    4. 先遍历背包，再遍历物品
    5. "leetcode", wordDict = ["leet", "code"]
       j=0    j=1    j=2    j=3    j=4    j=5    j=6    j=7    j=8
i=0    true   false  false  false  true   false  false  false  false 
i=1    true   false  false  false  false  false  false  false  true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public boolean wordBreak(String s, List<String> wordDict) {
    int length = s.length();
    Set<String> set = new HashSet<>();
    for (String str : wordDict) {
        set.add(str);
    }
    boolean[] dp = new boolean[length+1];
    dp[0] = true;
    for (int j=1; j<=length; j++) {
        for (int i=0; i<j; i++) {
            // dp[i] 前i个字符串
            // s.substring(i, j) 第i+1个字符串到第j个字符串(包括第j个)
            // 如果前i个字符串可以构成，第i+1到第j个字符串在单词内
            // 那么dp[j]也可以构成
            if (dp[i] && set.contains(s.substring(i, j))) {
                dp[j] = true;
                break;
            }
        }
    }
    return dp[length];
}

打家劫舍

打家劫舍Ⅰ

https://leetcode.cn/problems/house-robber/

1
2
3
4
5
6
7
1. dp[i] 打劫[0, i]的数组最大金钱树
2. 打劫当前值 nums[i] + dp[i-2] 不打劫当前值dp[i-1]
   dp[i] = Math.max(nums[i]+dp[i-2], dp[i-1])
3. dp[0] = nums[0] dp[1] = Math.max(nums[0], nums[1])
4. 前至后
5. [1,2,3,1]
dp 1 2 4 4
1
2
3
4
5
6
7
8
9
10
11
12
13
public int rob(int[] nums) {
    int length = nums.length;
    if (length == 1) {
        return nums[0];
    }
    int[] dp = new int[length];
    dp[0] = nums[0];
    dp[1] = Math.max(nums[0], nums[1]);
    for (int i=2; i<length; i++) {
        dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1]);
    }
    return dp[length-1];
}

打家劫舍Ⅱ

https://leetcode.cn/problems/house-robber-ii/

1
2
3
4
仍然是打家劫舍的逻辑，但是开头与结尾分别考虑
开头与结尾不能同时存在在数组中，
包含开头时，为了防止打劫结尾，不能包含结尾
包含结尾时，为了防止打劫开头，不能包含开头
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int rob(int[] nums) {
    int length = nums.length;
    if (length == 1) {
        return nums[0];
    }
    return Math.max(this.robRange(nums, 0, length-2), this.robRange(nums, 1, length-1));
}

private int robRange(int[] nums, int start, int end) {
    int length = end - start + 1;
    if (length == 1) {
        return nums[start];
    }
    int[] dp = new int[length];
    dp[0] = nums[start];
    dp[1] = Math.max(nums[start], nums[start+1]);
    for (int i=start+2; i<=end; i++) {
        dp[i-start] = Math.max(nums[i] + dp[i-2-start], dp[i-1-start]);
    }
    return dp[length-1];
}

打家劫舍Ⅲ

https://leetcode.cn/problems/house-robber-iii/

  • 递归(超时)
  1. 递归返回值以及参数
    int rob(root) 递归函数的意义很重要，就像dp[i]的意义一样，知道了rob的意义，就知道何时使用递归

rob函数的意义，抢劫root为根的树的最大值

  1. 递归终止条件
    当root为空时，什么都抢不到 0

root左右孩子都为空时，只能抢root，使收益最大，返回root.val

  1. 单层递归逻辑
    分两种情况，抢当前节点与不抢当前节点

抢当前节点的话，就不能抢儿子节点，抢当前节点的最大收益，就是当前节点的值+孙子一为根的树的最大值+孙子二为根的最大值+孙子三为根的最大值+孙子四为根的最大值

不抢当前节点的话，最大收益为 儿子一为根的最大值+儿子二为根的最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int rob(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {
        return root.val;
    }
    // 抢父节点，就不能抢左右儿子节点，但是孙子节点都可以考虑抢
    // 是考虑抢，不一定非要抢，是把孙子节点看成根，抢这个根的最大收益
    int val1 = root.val;
    if (root.left != null) {
        val1 += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right != null) {
        val1 += rob(root.right.left) + rob(root.right.right);
    }
    // 不抢父节点，左右儿子节点都可以考虑抢
    int val2 = rob(root.left) + rob(root.right);
    return Math.max(val1, val2);
}
  • 递归+记忆化
    打劫当前节点时，会计算孙子节点

不打劫当前节点时，会计算儿子节点，在计算儿子节点时，还会计算孙子节点，孙子节点重复计算了，可以使用map保存计算的结果

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
private Map<TreeNode, Integer> map = new HashMap<>();
public int rob(TreeNode root) {
    if (root == null) {
        return 0;
    }
    if (root.left == null && root.right == null) {
        return root.val;
    }
    // 如果计算过，直接返回计算结果
    if (this.map.get(root) != null) {
        return map.get(root);
    }

    // 抢父节点，就不能抢左右儿子节点，但是孙子节点都可以考虑抢
    // 是考虑抢，不一定非要抢，是把孙子节点看成根，抢这个根的最大收益
    int val1 = root.val;
    if (root.left != null) {
        val1 += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right != null) {
        val1 += rob(root.right.left) + rob(root.right.right);
    }
    // 不抢父节点，左右儿子节点都可以考虑抢
    int val2 = rob(root.left) + rob(root.right);
    // 保存当前结果
    this.map.put(root, Math.max(val1, val2));
    return this.map.get(root);
}
  • 树形dp
    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
    树形dp
    1. 函数参数以及返回值
    int[] robTree(TreeNode root)
    递归函数的意义非常重要，不够该函数意义比较明显
    不抢根节点，在当前树上获得的最大值；
    抢根节点，在当前树上获得的最大值；

    返回值是一个dp数组 
    dp[0] 表示不抢根节点，在当前树上获得的最大值；
    dp[1] 表示抢根节点，在当前树上获得的最大值；

    2. 递归终止条件
    节点为空时 返回[0, 0]

    3. 遍历顺序：后续遍历，根据左右孩子遍历的结果，确定当前节点值

    4. 单层递归逻辑
    抢当前节点，不能抢左右孩子 dp[1] = current + left[0] + right[0]
    不抢当前节点，可以抢左右孩子，但是也可以不抢，要取最大值
    dp[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1])

    5. 举例 [3,2,3,null,3,null,1]
     3                       [6, 7]
    / \                  /         \
    2   3              [3, 2]      [1, 3]
    \   \               \             \
     3   1            [0, 3]       [0, 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int rob(TreeNode root) {
    int[] result = this.robTree(root);
    return Math.max(result[0], result[1]);
}

private int[] robTree(TreeNode root) {
    if (root == null) {
        return new int[]{0, 0};
    }

    int[] left = robTree(root.left);
    int[] right = robTree(root.right);
    int dontRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    int rob = root.val + left[0] + right[0];
    return new int[] {dontRob, rob};
}
赏

谢谢你请我喝杯可乐

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

北科大计算机在读<br><br>爱好编程<br><br>热爱技术<br><br>喜欢折腾