leetcode 322. Coin Change硬币交换问题

题目详细

描述

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
Example 2:

Input: coins = [2], amount = 3
Output: -1

解法一

思路

这类动态规划问题属于给定一个定值，然后给出一组数组，然后在满足约束条件下的最大值，像这样问题的动态规划是指从定值开始的动态规划，从0到总的amount,动态规划问题一个数组dp[amount+1]，刚开始多有的dp[i] 元素值初始化为最大值。第一种方法是从上到下的动态规划问题:

1. 当i==0时表示总值为0 ，此时dp[0]==0；
   dp[i] 表示总量为i下最少的货币交换方案,既然是最少的情况，那么必然就是+1的情况，每种货比使用一张 ,所以加1，达到尽量少的目的。
   
   
2. dp[i] = min(dp[i-coins[0]]+1 ,dp[i-coins[1]]+1, dp[i-coins[2]]+1, dp[i-coins[最后一个元素]]+1，dp[i]) 1<<i<<amount, 其中

public class mini_coin_change {
    //bottom_up 求解方法
    //最小的硬币交换问题
    public int solution(int []nums,int amount){
        if(nums.length==0|| amount==0) return 0;
        Arrays.sort(nums);
        int [] dp= new int [nums.length+1];
        Arrays.fill(dp,amount+1);
        dp[0]=0;
        for(int i=1;i<=amount;++i)
        {
            for(int j=0;j<nums.length;++j)
            {
                    if(nums[j]<i)
                    {
                    // 决定是加入这块硬币还是不加入的情况 dp[i]-nums[j]+1，代表加入,
                    dp[i]还是保持原来的数值 
                        dp[i] =Math.min(dp[i-nums[j]]+1,dp[i]);
                    }
            }
        }
        return dp[amount]<amount+1 ?dp[amount]:amount;
    }

}

复杂度分析

• 空间复杂度为o(amount)
• 时间复杂度为o(amount * number of coin),效率不是很好，像这道题目空间复杂度是下降不了的，不像其他题目可以压缩空间复杂度，只用一个两个数记录整体情况

解法二

思路：BFS+backtrack求解最小值问题

递归方法，跟上楼梯问题一样的思路， 问题拆分，比如当amount=6的时候，有n种解决方案，其中n代表货币可兑换的种类数，然后逐步递归下去，剪枝的条件是amount =0 的时候，然后选取一条长度最小的路径，分支数为可供选择的货币数木，每种情况对应一种情况
从//其中coinChange 比如amount=6,共三种货币1，2，3 则第一次循环使用 F(6-1=5), F(4),F(3),其中
//F（6） = MinF(5), F(4), F(3)）+ 1,三种情况下的代码， res其中就代表每种情况下的返回值， 最后再加1操作，代码体：剪枝条件判断，for循环各种可能分支，判断选择最小的其中一个分支情况

代码（Java）

 
 public class Solution {
        public int coinChange(int[] coins, int amount) {        
        if (amount < 1) return 0;
        return coinChange(coins, amount, new int[amount]);
    }

    private int coinChange(int[] coins, int rem, int[] count) {
    //深度递归剪枝的条件要写在前面类似，类似全排列和subsets类型的问题
    //rem ==0 0
        if (rem < 0) return -1;
        if (rem == 0) return 0;
       // 这一步是正确的剪枝后的结果
        if (count[rem - 1] != 0) return count[rem - 1];
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
        
            int res = coinChange(coins, rem - coin, count);
            if(rem>=0)
                min=Math.min(res+1,min);
        }
        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];
    }
}