LeetCode—— 零钱兑换(DP)

题目描述

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

示例 1:

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

输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。

一、CPP

1. 动态规划法（自底向上）：

解题思路:详解见类型一：最值型

时间复杂度:O(mn)，n为传入数值，m是硬币种类数。
空间复杂度:O(1)。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {

        //初始化状态数组
        vector<int> f(amount+1);
        int coin_num = coins.size();

        //初始条件
        f[0] = 0;

        //从小到大计算每个值的值，便于递归使使用，返回最后一个需要的值，即f(amount)的值
        for(int i = 1;i<=amount;i++){
            //刚开始初始化为无穷大
            f[i] = INT_MAX;

            //计算“最后一枚”：f[i] = min(f[i-coin[0]] + 1,....,f[i-coin[n-1] + 1])
            for(int j=0;j<coin_num;j++){
                //保证要计算的值必须大于硬币的面额 && 需要的硬币的个数不能为正无穷,否则加1后溢出(防溢出)
                if(i>=coins[j] && f[i - coins[j]] != INT_MAX){
                    f[i] = min(f[i - coins[j]] + 1,f[i]);
                }
            }
        }

        if(f[amount] == INT_MAX){
            f[amount] = -1;
        }

        return f[amount];        
    }
};

2. 递归法（带备忘录/记忆数组）

解题思路:为了避免递归时重复计算，使用数组当作备忘录，实际上就是剪枝。

时间复杂度:O(mⁿ)。
空间复杂度:O(1)。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> memo(amount + 1, INT_MAX);
        memo[0] = 0;
        return coinChangeDFS(coins, amount, memo);
    }
    int coinChangeDFS(vector<int>& coins, int target, vector<int>& memo) {
        if (target < 0) return - 1;
        if (memo[target] != INT_MAX) return memo[target];
        for (int i = 0; i < coins.size(); ++i) {
            int tmp = coinChangeDFS(coins, target - coins[i], memo);
            if (tmp >= 0) memo[target] = min(memo[target], tmp + 1);
        }
        return memo[target] = (memo[target] == INT_MAX) ? -1 : memo[target];
    }
};

3. 递归法（自顶向下）：

解题思路:详解见类型一：最值型

时间复杂度:O(mⁿ)，n为传入数值，m是硬币种类数，子问题个数，即递归树中节点的总数。
空间复杂度:O(1)。

#include <iostream>
#include <cmath> 

using namespace std;

int f(int x){
    if(x==0){ return 0;}
    int res = 100000;  //无穷大
    
    if(x>=2){
        res = min(f(x-2) + 1,res);
    }
    if(x>=5){
        res = min(f(x-5) + 1,res);
    }
    if(x>=7){
        res = min(fun(x-7) + 1,res);
    }

    return res;
}

int main()
{   

    cout<<f(27);
    
    return 0;
}

部分参考自：
LeetCode精选回答
刷题大神博客

二、Java（动态规划法）

class Solution {
    public int coinChange(int[] coins, int amount) {
        
        int coin_num = coins.length;
        int [] f = new int[amount+1];

        f[0] = 0;

        for(int i = 1; i<=amount; i++){
            f[i] = Integer.MAX_VALUE;
            for(int j = 0; j< coin_num; j++){
                if(i>=coins[j] && f[i - coins[j]] != Integer.MAX_VALUE)
                {
                    f[i] = Math.min(f[i - coins[j]] + 1, f[i]);
                }
            }
        }

        return f[amount] = (f[amount] == Integer.MAX_VALUE) ? -1 : f[amount];
    }
}

三、Python（动态规划法）

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        f = [float("inf")] * (amount+1)
        coin_num = len(coins)

        f[0] = 0

        for i in range(1,amount+1):
            for j in range(coin_num):
                if i >= coins[j] and not math.isinf(f[i - coins[j]]):
                    f[i] = min(f[i], f[i -coins[j]] + 1)
        # python没有三元表达式
        return  -1 if math.isinf(f[amount]) else f[amount]

四、各语言及算法时间复杂度