lintcode740. 零钱兑换 2 完全背包

痛定思痛。 2023-07-25 12:49 127阅读 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 条评论，127人围观）

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

相关阅读

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

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

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

相关 LeetCode动态规划完全背包问题——322.零钱兑换

题目描述： [322. 零钱兑换][322.] 给你一个整数数组 `coins` ，表示不同面额的硬币；以及一个整数 `amount` ，表示总金额。计算并返回可以

本是古典何须时尚/ 2023年10月03日 19:08/ 0 赞/ 38 阅读

相关 LeetCode动态规划完全背包问题——518.零钱兑换II

题目描述： [518. 零钱兑换 II][518. _ II] 给你一个整数数组 `coins` 表示不同面额的硬币，另给一个整数 `amount` 表示总金额。请

雨点打透心脏的1/2处/ 2023年10月03日 19:08/ 0 赞/ 32 阅读

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

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

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

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

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

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

相关 lintcode 562. 背包问题 IV完全背包

给出 n 个物品, 以及一个数组, nums\[i\]代表第i个物品的大小, 保证大小均为正数并且没有重复, 正整数 target 表示背包的大小, 找到能填满背包的方案数。

叁歲伎倆/ 2023年07月25日 11:26/ 0 赞/ 30 阅读

相关零钱兑换

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

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

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

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

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

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

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

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

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

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

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