[LeetCode] 322. Coin Change | 变换硬币

题目来源:LeetCode: 322. Coin Change

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:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)
Example 2:
coins = [2], amount = 3
return -1.
Note:
You may assume that you have an infinite number of each kind of coin.

题目:变换不同数量不同金额的硬币,如何使得最终总金额等于特定值所需要的金币数量最少。

思路

  • 动态规划(Dynamic Programming)找到状态转移方程
    状态dp[x]表示总金额为x时所需的最少金币数,c表示当前硬币金额
    递推过程:
    1
    2
    3
    4
    5
    6
    7
    coins=[1,3,5]
    dp[0]=0
    dp[1]=dp[1-1]+1=dp[0]+1=1
    dp[2]=dp[2-1]+1=dp[1]+1=2
    dp[3]=dp[3-3]+1=dp[0]+1=1 or dp[3]=dp[3-1]+1=2+1=3 ===> dp[3]=1
    dp[4]=dp[4-1]+1=2 or dp[4]=dp[4-3]+1=dp[1]+1=2 ===> dp[4]=2
    dp[5]=dp[5-5]+1=1 or dp[5]=dp[5-3]+1=3 or dp[5]=dp[5-1]+1=3 ===> dp[5]=1

据规律得到状态转移方程为:dp[x]=min(dp[x-c]+1), c为可能的金币金额。

源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int coinChange(int* coins, int coinsSize, int amount) {
int i=0, j=0;
int *dp = (int *)malloc(sizeof(int)*(amount+1));
for(i=0; i<amount+1; i++) {
dp[i] = -1;
}
dp[0] = 0;
for(i=0; i<amount; i++) {
if (dp[i] < 0 )
continue;
for(j=0; j<coinsSize; j++) {
int amount_cur = i + coins[j];
if(amount_cur > amount)
continue;
if( dp[amount_cur] > dp[i]+1 || dp[amount_cur]<0 )
dp[amount_cur] = dp[i] + 1;
}
}
int res = dp[amount];
free(dp);
return res;
}

运行结果

180 / 180 test cases passed.
Status: Accepted
Runtime: 40 ms
Submitted: 0 minutes ago

You are here! Your runtime beats 61.28% of csubmissions.

总结

  • 动态规划问题要点在于:定义状态,确定状态转移方程。
  • 对于复杂问题,可简化数量,逐步推倒后可确定其状态转移方程。
  • C中函数内申请内存注意释放

参考文献

  1. 动态规划:从新手到专家