LeetCode-518. Coin Change 2

LeetCode-518. Coin Change 2

You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

Note: You can assume that

0 <= amount <= 50001 <= coin <= 5000the number of coins is less than 500the answer is guaranteed to fit into signed 32-bit integer

Example 1:

Input: amount = 5, coins = [1, 2, 5]Output: 4Explanation: there are four ways to make up the amount:5=55=2+2+15=2+1+1+15=1+1+1+1+1

Example 2:

Input: amount = 3, coins = [2]Output: 0Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:

Input: amount = 10, coins = [10] Output: 1

题解：

第一次WA：

想法是遍历coins，然后降序dp，每个dp[j]都在dp[j - coins[i]]上多增加了一枚硬币。

但是没有考虑到是否可取到问题，即dp[j - coins[i]]是否存在。

class Solution {public: int change(int amount, vector& coins) { int n = coins.size(); if (n == 0) { return 0; } if (amount == 0) { return 1; } vector dp(amount + 1, 0); for (int i = 0; i < n; i++) { for (int j = amount; j >= coins[i]; j--) { dp[j] += dp[j - coins[i]] + 1; } } return dp[amount]; }};

第一次一直没想通dp[0] = 1是为什么：dp[0]理解为组成0的各个硬币种类，只有一种情况：一枚硬币不拿，那么dp[0] = 1。

之后状态转移方程为：遍历coins，dp[j] += dp[j - coins[i]]。

class Solution {public: int change(int amount, vector& coins) { int n = coins.size(); if (amount == 0) { return 1; } vector dp(amount + 1, 0); dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = coins[i]; j <= amount; j++) { if (j >= coins[i]) { dp[j] += dp[j - coins[i]]; } } } return dp[amount]; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。