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

迈不过友情╰ 2022-06-03 03:13 98阅读 0赞

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note: You can assume that

0 <= amount <= 5000  
1 <= coin <= 5000  
the number of coins is less than 500  
the answer is guaranteed to fit into signed 32-bit integer  
Example 1:

Input: amount = 5, coins = \[1, 2, 5\]  
Output: 4  
Explanation: there are four ways to make up the amount:  
5=5  
5=2+2+1  
5=2+1+1+1  
5=1+1+1+1+1  
Example 2:

Input: amount = 3, coins = \[2\]  
Output: 0  
Explanation: the amount of 3 cannot be made up just with coins of 2.  
Example 3:

Input: amount = 10, coins = \[10\]  
Output: 1

本题题意很简单，最初想到的是DFS深度优先遍历的做法，后来看到了一个DP做法，

dp\[i\]表示组成钱数i的不同方法。其实最开始的时候，博主就想着用一维的dp数组来写，但是博主开始想的方法是把里面两个for循环调换了一个位置，结果计算的种类数要大于正确答案，所以一定要注意for循环的顺序不能搞反，

建议和这一道题[leetcode 322. Coin Change 类似背包问题][leetcode 322. Coin Change] 一起学习

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

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

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

还有[leetcode 474. Ones and Zeroes若干0和1组成字符串最大数量+动态规划DP+背包问题][leetcode 474. Ones and Zeroes_0_1_DP]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int change(int amount, vector<int>& coins) 
        {
            vector<int> dp(amount + 1, 0);
            dp[0] = 1;
            for (int coin : coins) 
            {
                for (int i = coin; i <= amount; ++i) 
                {
                    dp[i] += dp[i - coin];
                }
            }
            return dp[amount];
        }
    };

[leetcode 322. Coin Change]: http://blog.csdn.net/jackzhang_123/article/details/78150520
[leetcode 377. Combination Sum IV _ _ DP_ _ DFS]: http://blog.csdn.net/jackzhang_123/article/details/78174174
[leetcode 279. Perfect Squares _ _ _DP]: http://blog.csdn.net/jackzhang_123/article/details/78117843
[leetcode 474. Ones and Zeroes_0_1_DP]: http://blog.csdn.net/JackZhang_123/article/details/78781584