leetcode 322零钱兑换

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

题目大意：

使用几种硬币找零钱，每种硬币可多次使用，求所需硬币最少数目。若硬币之和不能等于零钱总数，输出-1.

解题思路：

用递归的动态规划解决

 1 class Solution {
 2 public:
 3     
 4     const int inf = 1000000000;
 5     vector<vector<int>> v;
 6     int search(vector<int>& coins, int amount, int idx) {
 7         if (amount == 0)
 8             return 0;
 9         if (idx >= coins.size() || amount < 0)
10             return inf;
11         if (v[idx][amount] >= 0)
12             return v[idx][amount];
13         int a = search(coins, amount - coins[idx], idx);
14         int b = search(coins, amount, idx + 1);
15         v[idx][amount] = min(a + 1, b);
16         return v[idx][amount];
17     }
18     
19     int coinChange(vector<int>& coins, int amount) {
20         v.resize(coins.size(), vector<int>(amount + 1, -1));
21         int ans = search(coins, amount, 0);
22         if (ans < inf)
23             return ans;
24         return -1;
25     }
26 };

方法二：迭代

定义一个大小为amount + 1的数组dp，dp[i]代表当总钱币数为i时可兑换的最少的钱币个数，

当i为0时只需要0个钱币，因此dp[0]等于0。

当求dp[k]时，先令dp[k]等于正无穷，然后遍历所有钱币，若钱币j币值coins[j]小于k，令dp[k] = min(dp[k - coins[j] ] + 1, dp[k])。

 1 class Solution {
 2 public:
 3     const int inf = 1000000000;
 4     vector<int> dp;
 5     int coinChange(vector<int>& coins, int amount) {
 6         int N = coins.size();
 7         dp.resize(amount + 1);
 8         dp[0] = 0;
 9         for (int i = 1; i <= amount; i++) {
10             dp[i] = inf;
11             for (int j = 0; j < N; j++) {
12                 if (coins[j] <= i)
13                     dp[i] = min(dp[i], dp[i - coins[j]] + 1);
14             }
15         }
16         if (dp[amount] == inf)
17             return -1;
18         return dp[amount];
19     }
20 };