dp 类找零钱类问题

这类问题，需要维护，之前的状态，当前的状态是 （当前 - 当前值） 的上一个状态的最值相关

零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:

输入: coins = [2], amount = 3
输出: -1

  // 贪心思想，零钱兑换， 和平方求和的题目类似
    public int coinChange(int[] coins, int amount) {
        if(coins == null || coins.length == 0){
            return -1;
        }
        Arrays.sort(coins);
        int[] dp = new int[amount+1];
        for (int i=1;i<amount+1;i++){
            int min = amount +1;
            for (int j=0;j<coins.length;j++){
                    if (coins[j] > i){
                        break;
                    }
                    // 只需要处理当前值得状态，不需要管怎么计算
                    min = Math.min(min,dp[i-coins[j]] + 1);
            }
            dp[i] = min;
        }
        if (dp[amount] == amount+1){
            return -1;
        }
        return dp[amount];
    }

279 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

示例 1:

输入: n = 12 输出: 3 解释: 12 = 4 + 4 + 4.

public int numSquares(int n) {
        int sqareLen = (int)(Math.sqrt(n));
        int[] numSqare = new int[sqareLen];
        for(int i=1;i<=sqareLen;i++){
            numSqare[i-1] = i * i;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2;i<=n;i++){
            int count = n+1;
            for(int j=0;j < sqareLen && numSqare[j]<= i;j++){
                count = Math.min(count,dp[i-numSqare[j]]+1);
            }
            dp[i] = count;
        }
        return dp[n];
    }

416. 分割等和子集

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

注意:

每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

 public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0){
            return false;
        }
        int sum = 0;
        for(int x:nums){
            sum += x;
        }
        if(sum % 2 == 1){
            return false;
        }
        // 使用背包问题的动态规划进行求解
        boolean[][] dp = new boolean[nums.length][sum/2+1];
        int target = sum/2;
        if(nums[0] <= target){
            dp[0][nums[0]] = true;
        }

        for(int i=1;i<nums.length;i++){
            for(int j=0;j<=target;j++){
                dp[i][j] = dp[i-1][j];
                if(nums[i]<=j){
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
                }
            }
            if(dp[i][target]){
                return true;
            }
        }
        return dp[nums.length-1][target];
    }