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

seo和网站建设那个先学做淘宝客需要自己建网站吗

seo和网站建设那个先学,做淘宝客需要自己建网站吗,ps做全屏网站画布要多大,企业如何做网站518. 零钱兑换 II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 3…

518. 零钱兑换 II

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。

示例 1:

输入:amount = 5, coins = [1, 2, 5]
输出:4
解释:有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入:amount = 3, coins = [2]
输出:0
解释:只用面额 2 的硬币不能凑成总金额 3 。

示例 3:

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

提示:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • coins 中的所有值 互不相同
  • 0 <= amount <= 5000

思路:

此问题属于 0-1背包 的 完全背包 ,解法和 0-1背包类似:

0 - 1背包问题(万能统一代码)

定义一个二维数组dp 存储硬币组合数,其中 dp[i][j] 表示前 i 个硬币 可以凑成总金额 为 j 的 硬币组合数

  • 每种硬币的数量是无限的,所以可以重复使用
  • 状态转移方程为:
    dp[i][j]=dp[i−1][j]+dp[i][j−coins[i]]dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i]]dp[i][j]=dp[i1][j]+dp[i][jcoins[i]]

示例1 的dp二维数组为:

在这里插入图片描述

观察前 i 个硬币的状态仅与前 i -1 个硬币的状态有关,因此可以优化,将 dp 定义为一维数组,其中 dp[j] 既可以表示 dp[i-1][j] 也可以表示 dp[i ][j - coins[i]]:状态转移方程为:
dp[j]+=dp[j−coins[i]]dp[j] += dp[j - coins[i]]dp[j]+=dp[jcoins[i]]

代码:(Java)

public class Change {public static void main(String[] args) {// TODO Auto-generated method stubint[] coins = {1, 2, 5};int amount = 5;System.out.println(change(amount, coins));}public static int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0] = 1;for(int coin : coins) {for(int i = coin; i <= amount; i++) {dp[i] += dp[i - coin];}}return dp[amount];}
}

运行结果:

在这里插入图片描述

复杂度分析:

  • 时间复杂度O(len∗amount)O(len * amount)O(lenamount), lenlenlen 为数组 coinscoinscoins 的长度,amountamountamount 为要凑成的总金额。
  • 空间复杂度O(amount)O(amount)O(amount) ,需要开辟一个一维数组 dp , 长度为amount+1amount + 1amount+1amountamountamount 为要凑成的总金额。

322. 零钱兑换 I

注:仅供学习参考 如有不足,欢迎指正!

题目来源:力扣。

http://www.yayakq.cn/news/292287/

相关文章:

  • 泉州企业网站制作定制做网站的客户哪里找
  • 桥梁建设设计网站wordpress md风格
  • 手机网站管理工具黑龙江省建设集团网站
  • 网站排名提升软件99国精产品灬源码的优势
  • 天河做网站哪家强wordpress插图插件
  • 成都工业学院文献检索在哪个网站做零基础 网站
  • 做IT的需要别人打开网站吗兰州新增94个高风险区
  • 帮助做ppt的网站四川建设厅官方网站九大员通知
  • 文化网站建设心得wordpress分类信息导航
  • 湖北省城建设计院网站网站数据分析报表
  • ppt的网站导航栏怎么做wordpress实现登录注册
  • 永兴网站制作成品网站超市源码
  • 广州正规网站建设公司方便做流程图的网站
  • 网站策划包括什么动态静态结合网站
  • 专做韩餐网站新闻类网站开发多久
  • 怎么样查看网站开发语言天津网站建设制作免费
  • 有没有做任务的网站吗05网补充答案全部
  • 如何在记事本中做网站链接php做视频分享网站
  • php做电商网站项目管理咨询公司
  • 会议网站建设的意义莱芜雪野湖介绍
  • 东莞百度seo在哪优化网络的软件
  • 做网站要注意哪些长沙本地推广
  • 图标的网站商城站时刻表
  • 阜平网站seo专业做网站公司怎么收费
  • 二手手机网站网页设计wordpress html伪静态
  • 沧州网站建设报价wordpress写 a href
  • 能直接看的网站有哪些信息流广告模板
  • 郑州微网站开发企业网站建设需要准备资料
  • 做网站 花时间网站qq访客抓取
  • 国家住房城乡建设厅网站设计师对网站的意义