当前位置:网站首页>Change exchange II - [leetcode]
Change exchange II - [leetcode]
2022-04-23 11:24:00 【D&Blogsphere_.】
class Solution {
// give an example amount = 5, coins = [1, 2, 5]
public int change(int amount, int[] coins) {
// Recursive expression
int[] dp = new int[amount + 1];
// initialization dp Array , Indicates that the amount is 0 There is only one case , That is to pretend nothing
dp[0] = 1;
for(int i = 0;i < coins.length; i++) {
// First traversal coins
//dp[j]: Make up the total amount j The number of currency combinations is dp[j]
// First round outer layer for loop , Show consideration coins[0]==1
// Make up the total amount 1 The number of currency combinations is dp[1] = dp[1] + dp[0]; ( Is to consider 1 And don't consider 1 The sum of ) At this point, you may think dp[1] What is the value , Actually dp When the array is initialized , It's worth it all 0 了 , So here dp[1] = dp[1] + dp[0] = 0 + 1 = 1
// When j++, after dp[2] = dp[2] + dp[2-1];( Is to consider 2 And don't consider 2 The sum of )
// Why initialize here j=coins[i]??
// consider j=coins[1] The situation of : here j==2, be dp[2] = dp[2] + dp[2-2];dp[3] = dp[3] + dp[3-2];
// Be careful : You may think of dp[3-2] What is the value ? yes 0 Do you ? No , Actually dp The array is in the last round for It's already right when you cycle dp The array is given a new value , Second round outer layer for The loop just changes the value based on the previous round ,dp An array is a dynamically changing array
for(int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
// // Print dp Array
// for(int i1 = 0; i1 < dp.length;i1++) {
// System.out.print(dp[i1]);
// }
// System.out.println();
}
return dp[amount];
}
}
版权声明
本文为[D&Blogsphere_.]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231119143370.html
边栏推荐
- 学习 Go 语言 0x01:从官网开始
- 解读机器人创造出来的艺术
- MySQL面试题讲解之如何设置Hash索引
- 采用百度飞桨EasyDL完成指定目标识别
- 学习 Go 语言 0x07:《Go 语言之旅》中 Stringer 练习题代码
- Facing the global market, platefarm today logs in to four major global platforms such as Huobi
- 少儿编程结构的改变之路
- 解析性能良好的机器人使用守则
- R-drop: a more powerful dropout regularization method
- Get things technology network optimization - CDN resource request Optimization Practice
猜你喜欢
随机推荐
mysql创建存储过程及函数详解
学习 Go 语言 0x04:《Go 语言之旅》中切片的练习题代码
AcWing 1874. 哞加密(枚举,哈希)
laravel编写Console脚本
进程间通信 -- 消息队列
Detailed explanation of integer data type tinyint in MySQL
实践数据湖iceberg 第三十课 mysql->iceberg,不同客户端有时区问题
PyTorch 神经网络训练器
Learn go language 0x04: Code of exercises sliced in go language journey
MySQL数据库事务transaction示例讲解教程
Usage record of map < qstring, bool >
ConstraintLayout布局
Résumé de la relation entre GPU, cuda et cudnn
让中小学生在快乐中学习的创客教育
@Valid, @ validated learning notes
讯飞2021年营收183亿:同比增41% 净利为15.56亿
26. Delete duplicates in ordered array
When the activity is in progress! Click the link to join the live studio to participate in "can AI really save energy?" Let's have a discussion!
Upgrade the functions available for cpolar intranet penetration
Learn go language 0x06: Fibonacci closure exercise code in go language journey