AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

硬币问题 -- 练习DP (笔记)

作者: 作者的头像   Tie ,  2019-09-06 00:31:01 ,  所有人可见 ,  阅读 1626


0


硬币问题(笔记)

  • 第一题

题目:已经给了硬币面值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]; 

    }
};

0 评论

App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息