硬币问题（笔记）

• 第一题：已经给了硬币面值1， 5， 11， 求凑出面值n的最少硬币数

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;
int n;
int coins[3] = {1, 5, 11};
int cost[N];

int main()
{
    cin >> n;
    memset(cost, 10000, sizeof cost);
    cost[0] = 0;

    for (int i = 1; i <= n; i ++ )
        for (int j = 0; j < 3; j ++ )
        // 如果 i = 1, 5, 11
        // 那么cost[i]会更新成cost[i - coins[j]] + 1 = cost[0] + 1 = 1
        // 不然的话会更新成 min(10000, cost[i - coins[j]] + 1)
            if (i >= coins[j]) cost[i] = min(cost[i], cost[i - coins[j]] + 1);

    cout << cost[n] << endl;
    return 0;
}

• 第二题

Coin Change 2

思路：完全背包DP + 优化

• 状态表示：f[i][j]表示所有由前i种硬币凑出来总钱数小于j的凑法
• 状态计算: 把最后一种硬币拿掉：f[i][j] = f[i-1][j-k*coins[i]], 这样的话时间复杂度是O(n^3)
• 优化： f[i][j] = f[i-1][j] + f[i-1][j-coins[i]] + f[i-1][j-2*coins[i]] + …
  • f[i][j-coins[i]] = f[i-1][j-coins[i]] + f[i-1][j-2*coins[i]] + …
  • f[j] = f[j] + f[j-coins[i]]
• 参考：yxc

题目

/*
 * @lc app=leetcode id=518 lang=cpp
 *
 * [518] Coin Change 2
 *
 * https://leetcode.com/problems/coin-change-2/description/
 *
 * algorithms
 * Medium (43.71%)
 * Likes:    892
 * Dislikes: 38
 * Total Accepted:    54.5K
 * Total Submissions: 123.8K
 * Testcase Example:  '5\n[1,2,5]'
 *
 * 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.
 * 
 * 
 * 
 * 
 * 
 * 
 * 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
 * 
 * 
 * 
 * 
 * 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
 * 
 * 
 */

/* 错误思路
class Solution {
public:
    int change(int amount, vector<int>& coins) {
        //切入点：考虑最后一个数, i从0到amonut，把最后一个数拿出来：
        //f[i]集合为f(i - coins[j]) + f(coins[i])
        //状态表示：f[i] 表示凑出i的所有情况的个数
        //状态计算：f[i] += f(i - coins[j]) + f(coins[j])

        vector<int> f(amount + 1);
        f[0] = 1;
        int n = coins.size();
        for (int i = 1; i <= amount; i ++ )
            for (int j = 0; j < n; j ++ )
            {   
                if (amount >= coins[j]) f[i] += f(i - coins[j]) + f(coins[j]);
            }
        return f(amount);  
    }
};
*/

正确代码：参考yxc

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        //状态表示：f[i][j]表示所有由前i种硬币凑出来总钱数小于j的凑法
        //状态计算: 把最后一种硬币拿掉：f[i][j] = f[i-1][j-k*coins[i]], 这样的话时间复杂度是O(n^3)
        //优化： f[i][j] = f[i-1][j] + f[i-1][j-coins[i]] + f[i-1][j-2*coins[i]] + ...
        //       f[i][j-coins[i]] =  f[i-1][j-coins[i]] + f[i-1][j-2*coins[i]] + ...
        // f[i][j] = f[i-1][j] + f[i][j-coins[i]]
        // f[j] = f[j] + f[j-coins[i]]
        int n = coins.size();
        vector<int> f(amount + 1);
        f[0] = 1;
        for (int i = 0; i < n; i ++ )
            for (int j = coins[i]; j <= amount; j ++ )
                f[j] += f[j - coins[i]];
        return f[amount]; 

    }
};