当前位置:网站首页>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
边栏推荐
- Mysql中有关Datetime和Timestamp的使用总结
- 防止web项目中的SQL注入
- 升级cpolar内网穿透能获得的功能
- 实践数据湖iceberg 第三十课 mysql->iceberg,不同客户端有时区问题
- Study notes of C [8] SQL [1]
- CUMCM 2021-b: preparation of C4 olefins by ethanol coupling (2)
- Laravel增加自定义助手函数
- laravel-admin表单验证
- 2022爱分析· 工业互联网厂商全景报告
- Upgrade the functions available for cpolar intranet penetration
猜你喜欢
随机推荐
得物技术网络优化-CDN资源请求优化实践
After the MySQL router is reinstalled, it reconnects to the cluster for boot - a problem that has been configured in this host before
GPU, CUDA,cuDNN三者的关系总结
Mysql8. 0 installation guide
Detailed explanation of integer data type tinyint in MySQL
2022爱分析· 工业互联网厂商全景报告
Promise details
MySQL对数据表已有表进行分区表的实现
laravel编写Console脚本
mysql插入datetime类型字段不加单引号插入不成功
Analysis on the characteristics of the official game economic model launched by platoffarm
Laravel绑定钉钉群警报(php)
MySQL分区表实现按月份归类
MySQL数据库10秒内插入百万条数据的实现
Use of SVN:
进程间通信 -- 消息队列
Mysql中有关Datetime和Timestamp的使用总结
卷积层和池化层总结
After the MySQL router is reinstalled, it reconnects to the cluster for boot - a problem that has been configured in this host before
rebbitMQ的简单搭建