lintcode 669. 换硬币完全背包

约定不等于承诺〃 2023-07-25 11:26 11阅读 0赞

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

样例
    样例1
    
    输入：
    [1, 2, 5]
    11
    输出： 3
    解释： 11 = 5 + 5 + 1
    样例2
    
    输入： 
    [2]
    3
    输出： -1
    注意事项
    你可以假设每种硬币均有无数个
    总金额不会超过10000
    硬币的种类数不会超过500, 每种硬币的面额不会超过100

class Solution {
        
    public:
        /**
         * @param coins: a list of integer
         * @param amount: a total amount of money amount
         * @return: the fewest number of coins that you need to make up
         */
        int coinChange(vector<int> &coins, int amount) {
        
            // write your code here
            vector<int> dp(amount+1,INT_MAX-1);
            dp[0]=0;
            for (int i = 0; i < coins.size(); i++) {
        
                for(int j = coins[i];j<=amount;j++)
                {
        
                    dp[j]=min(dp[j],dp[j-coins[i]]+1);
                }
            }
            if(dp[amount]==INT_MAX-1) return -1;
            return dp[amount];
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关算法-完全背包硬币组合问题

1. 硬币组合问题给定硬币的面值数组，以及需要找零的目标值 target，输出能满足要求的最小硬币数量。例如： coins = \[1, 2, 5\], amo...

ゞ浴缸里的玫瑰/ 2024年04月18日 14:58/ 0 赞/ 76 阅读

相关【容斥+完全背包】P1450 [HAOI2008] 硬币购物

[P1450 \[HAOI2008\] 硬币购物 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)][P1450 _HAOI2008_ _ - _ _ _ _l

不念不忘少年蓝@/ 2024年03月17日 09:00/ 0 赞/ 28 阅读

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

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

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

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

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

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

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

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

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

相关完全背包

完全背包在背包九讲中有很详细的讲解，但是今天碰到题尝试了一下他给的算法，发现并不快，看了一下其他的代码，速度很快！题目链接http://hihocoder.com/prob

拼搏现实的明天。/ 2022年08月21日 02:16/ 0 赞/ 205 阅读

相关背包问题-背包01-硬币找零

package 动态规划.背包01; import java.util.Arrays; import java.util.Scanner;

深藏阁楼爱情的钟/ 2022年07月12日 12:12/ 0 赞/ 195 阅读

相关 01背包,完全背包

01背包问题：一个背包总容量为V，现在有N个物品，第i个物品体积为weight\[i\]，价值为value\[i\]，现在往背包里面装东西，怎么装能使背包的内物品价值最大？

男娘i/ 2022年06月09日 04:16/ 0 赞/ 265 阅读

相关完全背包

完全背包和01背包的区别 > 01背包：有n个物品，每种物品只能被使用一次 > > 完全背包：有n个物品，每个物品可以被多次使用完全背包的递推公式可以由01背包的递推公

ゞ浴缸里的玫瑰/ 2022年06月08日 09:43/ 0 赞/ 206 阅读

相关完全背包

问题：有N种物品和一个容量为V的背包，每种物品都有无限件可用。第i种物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量

今天药忘吃喽~/ 2022年05月31日 01:05/ 0 赞/ 213 阅读