05-动态规划之背包问题

01背包&完全背包

01背包：装包时每种物体不可重复计算；（从右向左遍历）

完全背包：装包时每种物体可以有无限多个；（从左向右遍历）

模板：

//01背包
for (int i = 0; i < n; i++) {
    for (int j = m; j >= V[i]; j--) {
        f[j] = max(f[j], f[j-V[i]] + W[i]);
    }
}
//完全背包
for (int i = 0; i < n; i++) {
    for (int j = V[i]; j <= m; j++) {
        f[j] = max(f[j], f[j-V[i]] + W[i]);
    }
}

01背包

416. 分割等和子集

Difficulty: 中等

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

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

Solution

class Solution {
    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;
        }

        int target = sum/2;
        int[] dp = new int[target+1];
        dp[0] = 1;

        for(int num : nums){
            // 为什么这里必须要用--; 0-1背包，b
            for(int i = target; i >= num; i--){
                dp[i] += dp[i-num];
            }
        }

        return dp[target] != 0;
    }
}

完全背包

518. 零钱兑换 II

Difficulty: 中等

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1

提示：

• 1 <= coins.length <= 300
• 1 <= coins[i] <= 5000
• coins 中的所有值 互不相同
• 0 <= amount <= 5000

Solution

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, 0);
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }
}

42.接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
提示：

• n == height.length
• 0 <= n <= 3 * 10<sup>4</sup>
• 0 <= height[i] <= 10<sup>5</sup>

Solution

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if (height.length == 0)
            return 0;

        int[] leftMax = new int[n];
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(height[i], leftMax[i - 1]);
        }

        int[] rightMax = new int[n];
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(height[i], rightMax[i + 1]);
        }

        int ans = 0;
        for (int i = 1; i < n - 1; i++) {
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        return ans;

    }
}

升级蓄水池

通过增加某些墙壁的高度对蓄水池扩容，但是经费有限，最多只能增加最多m的高度，增加高度只能在【0-n】范围内，高度为0的区域也是可以增加的，为了追求最大的性价比，使扩容后蓄水池的容量最大

import java.util.*;

public class Main{
    private static int maxWater = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }
        int m = sc.nextInt();
        maxWater = Math.max(maxWater, trap(arr));
        dfs(0,arr,m);
        System.out.println(maxWater);
    }

    public static void dfs(int index, int[] array, int m){
        if(index >= array.length) return;
        if(m == 0){
            maxWater = Math.max(maxWater, trap(array));
        }
        for(int i = 0; i <= m; i++){
            array[index] += i;
            dfs(index+1,array,m-i);
            array[index] -= i;
        }
    }

    public static int trap(int[] array){
        int n = array.length;
        int ans = 0;

        int[] leftMax = new int[n];
        leftMax[0] = array[0];
        for(int i = 1; i < n; i++){
            leftMax[i] = Math.max(array[i], leftMax[i-1]);
        }

        int[] rightMax = new int[n];
        rightMax[n-1] = array[n-1];
        for(int j = n-2; j >= 0; j--){
            rightMax[j] = Math.max(rightMax[j+1],array[j]);
        }

        for(int i = 1; i < n-1; i++){
            ans += Math.min(leftMax[i], rightMax[i]) - array[i];
        }

        return ans;
    }
}

Solution