lintcode740. 零钱兑换 2 完全背包

痛定思痛。 2023-07-25 12:49 14阅读 0赞

给出不同面值的硬币以及总金额. 试写一函数来计算构成该总额的组合数量. 你可以假设每一种硬币你都有无限个.

样例
    样例1
    
    输入: amount = 10 和 coins = [10] 
    输出: 1
    样例2
    
    输入: amount = 8 和 coins = [2, 3, 8]
    输出: 3
    解释:
    有3种方法:
    8 = 8
    8 = 3 + 3 + 2
    8 = 2 + 2 + 2 + 2
    注意事项
    你可以做出以下假设:
    
    0 <= amount <= 5000
    
    1 <= coin <= 5000
    
    硬币种类不超过 500
    
    结果保证符合 32 位符号整数

class Solution {
        
    public:
        /**
         * @param amount: a total amount of money amount
         * @param coins: the denomination of each coin
         * @return: the number of combinations that make up the amount
         */
        int change(int amount, vector<int> &coins) {
        
            // write your code here
            vector<int>dp(amount+1,0);
            dp[0]=1;
            for (int i = 0; i < coins.size(); i++) {
        
                for(int j = coins[i];j<=amount;j++)
                {
        
                    dp[j]+=dp[j-coins[i]];
                }
            }
            return dp[amount];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，14人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法挨揍日记】day43——DP42 【模板】完全背包、322. 零钱兑换

DP42 【模板】完全背包 [【模板】完全背包\_牛客题霸\_牛客网][Link 1] 题目描述：描述你有一个背包，最多能容纳的体积是V。现在有

我不是女神ヾ/ 2024年02月05日 18:10/ 0 赞/ 72 阅读

相关动态规划-完全背包问题（纯完全背包、零钱兑换II、组合总数 IV、零钱兑换、完全平方数、单词拆分）、纯多重背包问题

1.完全背包问题（每件物品可放多次）有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight\[i\]，得到的价值是value\[i\] 。每件物品都有无

迈不过友情╰/ 2023年09月25日 18:30/ 0 赞/ 64 阅读

相关 lintcode740. 零钱兑换 2 完全背包

给出不同面值的硬币以及总金额. 试写一函数来计算构成该总额的组合数量. 你可以假设每一种硬币你都有无限个. 样例样例1 输入: amoun

痛定思痛。/ 2023年07月25日 12:49/ 0 赞/ 15 阅读

相关 lintcode 700. 杆子分割完全背包

给一个 n 英寸长的杆子和一个包含所有小于 n 的尺寸的价格. 确定通过切割杆并销售碎片可获得的最大值. 样例样例1 输入： [1

超、凢脫俗/ 2023年07月25日 12:35/ 0 赞/ 12 阅读

相关 lintcode 669. 换硬币完全背包

给出不同面额的硬币以及一个总金额. 写一个方法来计算给出的总金额可以换取的最少的硬币数量. 如果已有硬币的任意组合均无法与总金额面额相等, 那么返回 -1. 样例

约定不等于承诺〃/ 2023年07月25日 11:26/ 0 赞/ 12 阅读

相关零钱兑换

零钱兑换题目 > 题目地址：[https://leetcode-cn.com/problems/coin-change][https_leetcode-cn.co

旧城等待，/ 2023年02月11日 04:55/ 0 赞/ 37 阅读

相关零钱兑换

零钱兑换 1、参考资料 https://leetcode-cn.com/problems/coin-change/ https://labuladong.gitb

朴灿烈づ我的快乐病毒、/ 2022年12月04日 09:58/ 0 赞/ 195 阅读

相关背包型动态规划——零钱兑换

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

偏执的太偏执、/ 2022年10月27日 12:06/ 0 赞/ 202 阅读

相关 518 零钱兑换 II（完全背包问题）

1. 问题描述：给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑

系统管理员/ 2022年08月30日 04:12/ 0 赞/ 275 阅读

相关钱币兑换问题（完全背包）

钱币兑换问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

￡神魔★判官ぃ/ 2022年08月02日 14:53/ 0 赞/ 233 阅读