leetcode 322. Coin Change 类似背包问题 + 很简单的动态规划DP解决

末蓝、 2022-06-07 01:09 161阅读 0赞

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:  
coins = \[1, 2, 5\], amount = 11  
return 3 (11 = 5 + 5 + 1)

Example 2:  
coins = \[2\], amount = 3  
return -1.

Note:  
You may assume that you have an infinite number of each kind of coin.

第一感觉就是一个简单的DP应用，所以这里就不介绍了，类似背包问题。

建议和这一道题[leetcode 518. Coin Change 2 动态规划DP][leetcode 518. Coin Change 2 _DP] 一起学习

**这两到的DP的出发点是不一样的，本题是尽量凑够amout，然后求解最小的数量，518则是求解能够组成amount的所有的情况的计数，所以这两道题很类似，但是不一样**

还建议和[leetcode 279. Perfect Squares 类似背包问题 + 很简单的动态规划DP解决][leetcode 279. Perfect Squares _ _ _DP] 一起学习

还有这一道题[leetcode 377. Combination Sum IV 组合之和 + DP动态规划 + DFS深度优先遍历][leetcode 377. Combination Sum IV _ _ DP_ _ DFS]和[leetcode 416. Partition Equal Subset Sum 动态规划DP + 深度优先遍历DFS][leetcode 416. Partition Equal Subset Sum _DP _ _DFS]一起学习

还有 [leetcode 494. Target Sum目标和 + 背包问题 + 深度优先遍历DFS + 动态规划DP + 简单的分析推导 ][leetcode 494. Target Sum_ _ _ _ _DFS _ _DP _ _]

代码如下：

import java.util.Arrays;
    
    /*
     * 这就是一个简单的DP应用
     * */
    class Solution 
    {
        public int coinChange(int[] coins, int amount) 
        {
            if(coins==null||coins.length<=0 || amount<0)
                return -1;
    
            int[] dp=new int[amount+1];
            //注意这里使用的是amount+1作为上限的
            //不能用Integer.MAX_VALUE，因为会越界
            Arrays.fill(dp, amount+1);
            dp[0]=0;
            for(int i=1;i<=amount;i++)
            {
                for(int j=0;j<coins.length;j++)
                {
                    if(i>=coins[j])
                        dp[i]=Math.min(dp[i], dp[i-coins[j]]+1);  
                }
            }        
            return dp[amount]==amount+1? -1 : dp[amount];
        }
    }

下面是C++的做法

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    
    using namespace std;
    
    
    class Solution 
    {
    public:
        int coinChange(vector<int>& coins, int amount)
        {
            vector<int> dp(amount + 1,amount+1);
            dp[0] = 0;
            for (int i = 1; i <= amount; i++)
            {
                for (int j = 0; j < coins.size(); j++)
                {
                    if (i >= coins[j])
                        dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
            return dp[amount] == amount + 1 ? -1 : dp[amount];
        }
    };

[leetcode 518. Coin Change 2 _DP]: http://blog.csdn.net/JackZhang_123/article/details/78820585
[leetcode 279. Perfect Squares _ _ _DP]: http://blog.csdn.net/jackzhang_123/article/details/78117843
[leetcode 377. Combination Sum IV _ _ DP_ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78174174
[leetcode 416. Partition Equal Subset Sum _DP _ _DFS]: http://blog.csdn.net/jackzhang_123/article/details/78752598
[leetcode 494. Target Sum_ _ _ _ _DFS _ _DP _ _]: http://blog.csdn.net/jackzhang_123/article/details/78793365