leetcode背包问题总结

01背包

446 分割等和字集

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        int maxn = Arrays.stream(nums).max().getAsInt();
        int half = sum / 2;
        if (sum % 2 != 0 || maxn > half) {
            return false;
        }
        int[] dp = new int[half+1];
        Arrays.sort(nums);
        for (int i=0;i<nums.length;++i) {
            for (int j=half;j>=nums[i];--j) {
                dp[j] = Math.max(dp[j],dp[j-nums[i]]+nums[i]);
                if (dp[half] == half) {
                    return true;
                }
            }
        }
        return dp[half] == half;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

这一道题，是典型的动态规划题，在进行前置的判断后(数组总和是否为奇数，数组最大值是否大于数组总和一半)，我们设置half为数组的总和的一半，接下来开一个数组，数组的长度为half+1, 数组每一个所在的位置的元素代表能够填满该元素值(等于索引)的最大数量，我们需要预先对子集进行排序，然后依次去更新数组，在更新的过程中，只要发现dp[half]==half，说明可以分割为两个相同的子集

1049 最后一块石头的重量

class Solution {
    public int lastStoneWeightII(int[] garbages) {
        int sum = Arrays.stream(garbages).sum();
        int half = sum / 2;
        int[] dp = new int[half+1];
        Arrays.sort(garbages);
        for (int i=0;i<garbages.length;++i) {
            for (int j=half;j>=garbages[i];--j) {
                dp[j] = Math.max(dp[j],dp[j-garbages[i]]+garbages[i]);
            }
        }
        return sum - 2 * dp[half];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这道题和上一题似曾相识，因为石头的总重量是守恒的，所以最后我们能够获得填满dp[half]的最大值，通过此算出需要粉碎的差值

494 目标和

这道题也有暴力的方法

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums,0,target);
    }

    public int dfs(int[] nums,int i,int target) {
        if (i == nums.length) {
            return target == 0 ? 1 : 0;
        }
        return dfs(nums,i+1,target - nums[i]) + dfs(nums,i+1,target + nums[i] );
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

使用背包来做的吧

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = Arrays.stream(nums).sum();
        if ((target + sum) % 2 != 0) return 0;
        int size = (target + sum) / 2;
        if(size < 0) size = -size;
        int[] dp = new int[size + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = size; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[size];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

474 一和零

1

完全背包

322 零钱兑换

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 判断边界条件
        if (coins.length == 1) {
            return amount % coins[0] == 0 ? amount / coins[0] : -1;
        }
        int[] dp = new int[amount + 1];
        dp[0] = 0;
        for (int i=1;i<dp.length;++i) {
            dp[i] = amount + 1;
        }
        for (int i=0;i<coins.length;++i) {
            for (int j=0;j<=amount;++j) {
                if (j >= coins[i]) {
                    dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        return dp[amount] == amount + 1 ? -1 : dp[amount];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

518 零钱兑换二

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13

377 组合总和三

70 爬楼梯

279 完全平方数

class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        int _max = n;
        Arrays.fill(dp,_max);
        dp[0] = 0;
        for (int i=0;i<=n;++i) {
            for (int j=1;j*j<=i;++j) {
                dp[i] = Math.min(dp[i-j*j]+1,dp[i]);
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

139 单词拆分

public class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> wordDictSet = new HashSet(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16