背包问题思想的运用

 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

class Solution {
    public boolean canPartition(int[] nums) {
        if (nums == null || nums.length < 0)
            return false;
        int sum = 0;
        int N = nums.length;
        for (int i = 0; i < N; i++) {
            sum += nums[i];
        }
        if (sum % 2 != 0)
            return false;
        sum /= 2;
        int[] dp = new int[sum + 1];
        for (int i = 1; i <= sum; i++)
            dp[i] = -Integer.MAX_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = sum; j >= nums[i]; j--)
                dp[j] = Math.max(dp[j], dp[j-nums[i]]);
        }
        return dp[sum] == 0 ? true : false;
    }
    
    boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        // 和为奇数时，不可能划分成两个和相等的集合
        if (sum % 2 != 0) return false;
        int n = nums.length;
        sum = sum / 2;
        boolean[] dp = new boolean[sum + 1];

        // base case
        dp[0] = true;

        for (int i = 0; i < n; i++) {
            for (int j = sum; j >= 0; j--) {
                if (j - nums[i] >= 0) {
                    dp[j] = dp[j] || dp[j - nums[i]];
                }
            }
        }
        return dp[sum];
    }
}

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

class Solution {

    public int findTargetSumWays(int[] nums, int target) {
        return backtracking(nums, 0, 0, target);
    }

    private int backtracking(int[] nums, int index, int sum, int target) {
        if (index == nums.length) {
            if (sum == target) {
                return 1;
            } else {
                return 0;
            }
        }
        return backtracking(nums, index+1, sum + nums[index], target) + 
                    backtracking(nums, index+1, sum - nums[index], target);
    }
}

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

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        if (nums == null || nums.length == 0)
            return 0;
        int sum = target;
        int N = nums.length;
        for (int i = 0; i < N; i++)
            sum += nums[i];
        if (sum < 0 || sum % 2 == 1)
            return 0;
        sum /= 2;
        int[] dp = new int[sum+1];
        dp[0] = 1;
        for (int i = 0; i < N; i++) {
            for (int j = sum; j >= nums[i]; j--)
                dp[j] += dp[j-nums[i]];
        }
        return dp[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

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m+1][n+1];
        int len = strs.length;
        for (int i = 0; i < len; i++) {
            int countZero = getCount(strs[i], '0');
            int countOne = getCount(strs[i], '1');
            for (int j = m; j >= countZero; j--) {
                for (int k = n; k >= countOne; k--) {
                    dp[j][k] = Math.max(dp[j][k], dp[j-countZero][k-countOne] + 1);
                }
            }
        }
        return dp[m][n];
    }

    public int getCount(String str, char ch) {
        int ret = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == ch)
                ret++;
        }
        return ret;
    }
}

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

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        for (int i = 1; i <= amount; i++)
            dp[i] = amount+1;
        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++)
                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

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    // 数组大小为 amount + 1，初始值也为 amount + 1
    Arrays.fill(dp, amount + 1);

    // base case
    dp[0] = 0;
    // 外层 for 循环在遍历所有状态的所有取值
    for (int i = 0; i < dp.length; i++) {
        // 内层 for 循环在求所有选择的最小值
        for (int coin : coins) {
            // 子问题无解，跳过
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount];
}

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

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