新浦网站制作,不同网站对商家做o2o的政策,网站开发需要20万,南通有哪些网站2024.3.25 题目来源我的题解方法一 动态规划 题目来源
力扣每日一题#xff1b;题序#xff1a;518
我的题解
方法一 动态规划 给定总金额 amount 和数组 coins#xff0c;要求计算金额之和等于 amount 的硬币组合数。其中#xff0c;coins的每个元素可以选取多次#… 2024.3.25 题目来源我的题解方法一 动态规划 题目来源
力扣每日一题题序518
我的题解
方法一 动态规划 给定总金额 amount 和数组 coins要求计算金额之和等于 amount 的硬币组合数。其中coins的每个元素可以选取多次且不考虑选取元素的顺序因此这道题需要计算的是选取硬币的组合数。 可以通过动态规划的方法计算可能的组合数。用 dp[x]表示金额之和等于 x的硬币组合数目标是求 dp[amount]。 动态规划的边界是 dp[0]1。只有当不选取任何硬币时金额之和才为 0因此只有 1 种硬币组合。 对于面额为 coin 的硬币当 coin≤i≤amount时如果存在一种硬币组合的金额之和等于 i−coin则在该硬币组合中增加一个面额为 coin的硬币即可得到一种金额之和等于 i 的硬币组合。因此需要遍历 coins对于其中的每一种面额的硬币更新数组 dp中的每个大于或等于该面额的元素的值。 时间复杂度O(Sn)。S是需要匹配的金额n为面额数 空间复杂度O(S) public int change(int amount, int[] coins) {int[] dpnew int[amount1];//只有当不选取任何硬币时金额之和才为 000因此只有 111 种硬币组合。dp[0]1;//因为外层循环是遍历数组 coins 的值内层循环是遍历不同的金额之和在计算 dp[i]的值时可以确保金额之和等于 i 的硬币面额的顺序由于顺序确定因此不会重复计算不同的排列。for(int coin:coins){for(int icoin;iamount;i){dp[i]dp[i-coin];}}return dp[amount];}有任何问题欢迎评论区交流欢迎评论区提供其它解题思路代码也可以点个赞支持一下作者哈~
