leetcode hot100零钱兑换Ⅱ

news/2024/4/25 11:50:08

在这里插入图片描述
本题可以看出也是背包问题,但区别于之前的01背包问题,这个是完全背包问题的变形形式。

下面介绍01背包和完全背包的区别与联系:

  1. 01背包是背包中的物品只能用一次,不可以重复使用,而完全背包则是可以重复使用。
  2. 01/完全背包的递推公式(这里都是以一维数组的情况举例)是dp[j] = Math.max(dp[j],dp[j-weight[i]]+values[i])。
  3. 01背包的遍历顺序是先物品,再背包,并且背包遍历的时候是需要倒序遍历的,而完全背包则不需要,直接先物品再背包(背包需要正序),其实先背包再物品也可以,但为了方便记忆则和01保持一致。

而当在完全背包的变形形式,比如本题是要求组合数,组合是没有顺序的,只需要找出对应的元素就可以,所以递推公式是dp[j] += dp[j-nums[i]]。

所以本题中,我们可以想将背包中的硬币个数,不限制次数的选取,最后求凑成金额为amount的种类一共有多少种。

所以采用动态规划完全背包求组合情况

dp[j]表示背包容量为j的价值为dp[j]。
dp[j] += dp[j-nums[i]]
dp[0] = 1 (注意,这里必须是1,如果不是1的话没办法推出后面的数据,后面数据就都变成0了)。
遍历顺序应该先物品再背包,并且背包内层循环应该由小到大遍历。
打印

class Solution {public int change(int amount, int[] coins) {//递推表达式int[] dp = new int[amount + 1];//初始化dp数组,表示金额为0时只有一种情况,也就是什么都不装dp[0] = 1;for (int i = 0; i < coins.length; i++) {for (int j = coins[i]; j <= amount; j++) {dp[j] += dp[j - coins[i]];}}return dp[amount];}
}

注意:
如果求组合数就是外层for循环遍历物品,内层for遍历背包。
如果求排列数就是外层for遍历背包,内层for循环遍历物品。


https://www.xjx100.cn/news/3280706.html

相关文章

HTML元素和属性快速参考指南

​ 以下是几个与HTML元素和属性相关的参考资料网站链接&#xff1a; HTML Reference - 提供所有HTML元素和属性的免费指南。W3Schools HTML Reference - W3Schools 提供一个广泛的HTML标签和属性参考。freeCodeCamp HTML Cheat Sheet - freeCodeCamp 提供了一个HTML元素列表参…

AI之Sora:Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略

AI之Sora&#xff1a;Sora(文本指令生成视频的里程碑模型)的简介(能力/安全性/技术细节)、使用方法、案例应用之详细攻略 导读&#xff1a;Sora 是OpenAI研发的一个可以根据文字描述生成视频的AI模型。它的主要特性、功能以及OpenAI在安全和应用方面的策略的核心要点如下所示&a…

小程序--本地存储API

1、存储数据 wx.setStorageSync()&#xff1a;无需转换数据类型&#xff0c;存什么类型的就是什么类型的&#xff0c;data中的数据&#xff0c;使用时是this.data.名称。 saveData() {wx.setStorageSync(list, this.data.list)wx.showToast({title: 存储成功,})}, 2、读取数据…

java开源xml工具类介绍

在Java中处理XML的常用开源工具有很多&#xff0c;以下是一些流行的库以及简单的示例代码&#xff1a; DOM4J DOM4J 是一个非常流行的Java库&#xff0c;用于处理XML&#xff0c;DOM4J 易于使用&#xff0c;并且提供了很好的性能。 Maven 依赖 …

视频推拉流EasyDSS视频直播点播平台授权出现激活码无效并报错400是什么原因?

视频推拉流EasyDSS视频直播点播平台集视频直播、点播、转码、管理、录像、检索、时移回看等功能于一体&#xff0c;可提供音视频采集、视频推拉流、播放H.265编码视频、存储、分发等视频能力服务&#xff0c;在应用场景上&#xff0c;平台可以运用在互联网教育、在线课堂、游戏…

【Redis】理论进阶篇------Redis的持久化

一、前言 前面学习了Redis的相关的十大数据类型以及用SpringBoot集成我们的Redis的工具代码的书写。从这篇文章开始&#xff0c;就会从Redis相关的一些理论&#xff08;也是面试和工作的热点知识&#xff09;如&#xff1a;Redis的持久化、Redis的订阅发布模型、Redis集群环境搭…

【动态规划专栏】专题二:路径问题--------6.地下城游戏

本专栏内容为&#xff1a;算法学习专栏&#xff0c;分为优选算法专栏&#xff0c;贪心算法专栏&#xff0c;动态规划专栏以及递归&#xff0c;搜索与回溯算法专栏四部分。 通过本专栏的深入学习&#xff0c;你可以了解并掌握算法。 &#x1f493;博主csdn个人主页&#xff1a;小…

多维时序 | Matlab实现BiLSTM-MATT双向长短期记忆神经网络融合多头注意力多变量时间序列预测模型

多维时序 | Matlab实现BiLSTM-MATT双向长短期记忆神经网络融合多头注意力多变量时间序列预测模型 目录 多维时序 | Matlab实现BiLSTM-MATT双向长短期记忆神经网络融合多头注意力多变量时间序列预测模型预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.多维时序 | Matlab…