LeetCode322. Coin Change

LeetCode322. Coin Change

分析

1、base case

当目标金额amount 为0时，不需要任何硬币即可凑出。

2、状态

状态是会变化的量，这里显然有目标金额amount需要不断减少，向base case靠近，所以amount是唯一的状态。

3、选择

选择是导致状态变化的行为。我们需要对所有的硬币做尝试，选出能使硬币个数最少的方案。

4、定义dp函数/数组

这里自顶向下的解法定义为：

dp(n) = x: 表示目标金额为n时，至少需要x个硬才币可以凑出。

由此写出状态转移方程：

递归解法

class Solution {
public:
    int dp(vector<int>& coins, int amount, vector<int>& memo){
        if(amount==0) return 0;
        if(amount<0) return -1;
        //已经计算过，直接返回
        if(memo[amount] != 0) return memo[amount];
        //未计算过则计算
        int res = INT_MAX;
        for(int coin : coins){
            int sub = dp(coins,amount - coin ,memo);
            if(sub==-1) continue;
            res = min(res,sub+1); 
        }
        //更新memo
        memo[amount] = (res==INT_MAX)? -1 : res;
        return memo[amount];
    }

    int coinChange(vector<int>& coins, int amount) {
        if(amount==0) return 0;
        //memo[n] = x ：amount= n的钱至少需要x个硬币凑出来
        vector<int> memo(amount+1,0);
        return dp(coins, amount, memo);
    }
};

这里设的备忘录memo。

递归算法的时间复杂度为 子问题总数 x 每个子问题的时间。

子问题总数不超过金额数n，即子问题数目O(n)，处理一个子问题需要一个for循环，设时间O(k)。所以总时间复杂度为O(n*k)。

迭代解法

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(amount==0) return 0;
        //硬币面额为整数，即最小为1
        //所以硬币个数dp[?]最大不会超过目标金额数
        vector<int> dp(amount+1,amount+1);
        //base case
        dp[0] = 0;

        for(int i = 0 ;i < dp.size(); ++i){
            for(int coin:coins){
                if(i-coin<0) continue;
                dp[i] = min(dp[i], 1+dp[i-coin]);
            }
        }
        return (dp[amount] == amount+1) ? -1 : dp[amount];
    }
};

dp 数组的定义：当目标金额为 i 时，至少需要 dp[i] 枚硬币凑出。