当前位置: 首页 > news >正文

手机端怎么网站建设南京seo公司

手机端怎么网站建设,南京seo公司,体验比较好的网站,wordpress博客论坛插件大家好!我是曾续缘🤪 今天是《LeetCode 热题 100》系列 发车第 85 天 动态规划第 5 题 ❤️点赞 👍 收藏 ⭐再看,养成习惯 零钱兑换 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount &…

大家好!我是曾续缘🤪

今天是《LeetCode 热题 100》系列

发车第 85 天

动态规划第 5 题

❤️点赞 👍 收藏 ⭐再看,养成习惯

零钱兑换

给你一个整数数组 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
难度:💖💖

解题方法

我们可以使用动态规划来解决这个问题。首先创建一个长度为 amount + 1 的数组 dp,其中 dp[i] 表示凑齐金额 i 所需要的最少硬币个数。初始化将 dp 数组所有元素值设为 amount + 1,这个值相当于无穷大,用来表示不可能凑齐该金额。

然后,我们从金额 1 开始遍历到 amount,对于每个金额 i,再遍历硬币数组 coins 中的每个硬币面额 coins[j]。如果当前硬币面额 coins[j] 小于等于当前金额 i,则更新 dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1),即当前金额 i 所需的最少硬币个数为当前值和减去当前硬币面额后的金额所需硬币个数加一的较小值。

最终返回 dp[amount],如果其值大于 amount,表示无法凑齐该金额,返回 -1;否则返回 dp[amount]

Code

public class Solution {public int coinChange(int[] coins, int amount) {// 初始化最大值为 amount + 1int max = amount + 1;// 创建 dp 数组,记录凑齐各个金额所需的最少硬币个数int[] dp = new int[amount + 1];// 将 dp 数组所有元素值设为 maxArrays.fill(dp, max);// 初始金额为 0 时,所需硬币个数为 0dp[0] = 0;// 遍历金额从 1 到 amountfor (int i = 1; i <= amount; i++) {// 遍历硬币数组for (int j = 0; j < coins.length; j++) {// 如果当前硬币面额小于等于当前金额if (coins[j] <= i) {// 更新最少硬币个数dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);}}}// 返回最终结果,若大于 amount 则无法凑齐,返回 -1,否则返回 dp[amount]return dp[amount] > amount ? -1 : dp[amount];}
}
http://www.yayakq.cn/news/324864/

相关文章:

  • 铁总建设函网站长沙网站设计工作室
  • 零遁nas做网站安徽网新科技有限公司网站开发
  • 网站建设合同应注意手机百度账号申请注册
  • 苏州网站建设专业的公司网站建设流程所用工具
  • 网站建设如何做账个人网站建设免费主机
  • 网站开发课程内部培训个人建网站一般多少钱?
  • 北京h5网站制作综合权重查询
  • 江西南昌建设厅网站20平办公室装修设计
  • 江西省城乡建设厅网站证件查询杭州智能模板建站
  • 设计类网站策划书彭州做网站的公司
  • 网页设计入门书籍百度关键词排名优化工具
  • 专业创建网站公司宁波做百度网站
  • 大学生兼职网站策划书婴儿睡袋网站建设
  • 网站开发 用户角色网站建设与代运营介绍
  • 青羊区网站建设个人网站风格
  • 互联网站建设机构国际原油价格最新实时消息
  • 比较有名的设计网站镇江平台公司
  • 域名和网站培训网站建设报价单
  • 苏州市建设中心网站首页中山专业外贸网站开发公司
  • 哪里有网站建设加工企业设计网页
  • 站长工具在线查询贵阳个人做网站
  • Wordpress做什么网站赚钱展厅效果图网站
  • 深圳外贸建站模版即刻搜索
  • 网站关键词google优化怎么做免费建造公司网站
  • 网站开发外包协议360免费wifi无法在win10下正常运行
  • 自助定制网站开发公司外链推广是什么意思
  • 搭建网站视频教程怎样创办网站
  • 免费建设网站赚钱万能浏览器手机版下载安装2022
  • 如何注册chn域名网站做网站要不要用jsp
  • 店铺头像logo设计枫树seo