首页 > 其他分享 >322. 零钱兑换 ---- 动态规划

322. 零钱兑换 ---- 动态规划

时间:2022-11-13 16:56:09浏览次数:50  
标签:322 示例 int coins ---- 零钱 amount 硬币 dp

给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1 。

你可以认为每种硬币的数量是无限的。

 

示例 1:

输入:coins = [1, 2, 5], amount = 11
输出:3
解释:11 = 5 + 5 + 1
示例 2:

输入:coins = [2], amount = 3
输出:-1
示例 3:

输入:coins = [1], amount = 0
输出:0
 

提示:

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        // 数组大小为 amount + 1,初始值也为 amount + 1
        vector<int> dp(amount + 1, amount + 1);
        // base case
        dp[0] = 0;
        // 外层 for 循环在遍历所有状态的所有取值
        for (int i = 0; i < dp.size(); i++) {
            // 内层 for 循环在求所有选择的最小值
            for (int coin : coins) {
                // 子问题无解,跳过
                if (i - coin < 0) continue;
                dp[i] = min(dp[i], 1 + dp[i - coin]);
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
};

 

标签:322,示例,int,coins,----,零钱,amount,硬币,dp
From: https://www.cnblogs.com/slowlydance2me/p/16886279.html

相关文章

  • 网络流学习笔记
    基础知识定义网络\(G=(V,E)\)为有向图,边上有一权值\(c(x,y)\)为边的容量,有\(\forall(x,y)\notinE,c(x,y)=0\)。设定两个特殊的节点\(S\)源点和\(T\)......
  • 前端工程化
    前端工程化是指:在企业级的前端项目开发中,把前端开发所需的工具、技术、流程、经验等进行规范化、标准化。一、版本管理1、概念版本控制是一种软件工程技巧,借此能在软件......
  • 软件工程第二次实验
    实验过程1.本人角色本人在本次实验中担任驾驶员;姓名:邢巧巧   学号:223201062209我的结队伙伴是:庞玮洋2232010622302.任务分工驾驶员:邢巧巧博客链接:l 负责四则......
  • 能力提升综合题单-模拟,前缀和差分 题解
    好久没有写题解了,今天回来了!!A-铺地毯在luogu,享受coding的快乐见到题以后,一道水题直接模拟二位数组。。。《真·ACcode》:点击查看代码#include<bits/stdc++.h>u......
  • 【Java】Java中StringBuilder()成员方法append()和toString()
    StringBuilder就相当于C++的String长度可变,用于构造字符串对象,内部使用自动扩容的数组操作字符串数据。StringBuilder和StringBuffer使用的是相同的API【区别单独开一篇来......
  • 实验三:朴素贝叶斯算法
    |20大数据三班|首页-20级大数据3班机器学习-池州学院-班级博客-博客园(cnblogs.com)||201613328|博客后台-博客园(cnblogs.com)|【实验目的】理解朴素贝叶......
  • re正则--匹配方法
    --re.match()方法语法:re.match(pattern,string,flags) 其中flags表示的标志位。有以下几种re.I忽略大小写re.L表示特殊字符集\w,\W,\b,\B,\s,\S依赖于当前环......
  • Vue路由守卫操作-全局路由守卫
     先上代码:router.beforeEach=全局路由守卫//这个东西叫做路由守卫//在我们浏览器上面输入了url地址以后跳转到一个组件去router.beforeEach((to,from,next)=>......
  • 第2-2-4章 常见组件与中台化-常用组件服务介绍-分布式ID-附Snowflake雪花算法的代码实
    目录2.3分布式ID2.3.1功能概述2.3.2应用场景2.3.3使用说明2.3.4项目截图2.3.5Snowflake雪花算法的代码实现2.3分布式ID2.3.1功能概述ID,全称Identifier,中文翻译......
  • OpenGL ES glad 下载和使用
    目录一.glad简介二.glad下载四.glad使用1.OpenGLglfw+glad效果演示2.OpenGLglfw+glad《源码下载》二.猜你喜欢零基础OpenGLES学习路线推荐:O......