leetcode-518. 零钱兑换 II

1. 题目

链接: 零钱兑换II

2. 解决方案1

#include 
#include 

int change(int amount, int* coins, int coinsSize){
    int dp[amount+1];//确定dp大小
    memset(dp, 0, sizeof(int) * (amount+1));
    dp[0] = 1;//初始化为0
    for(int i = 0 ; i < coinsSize; i++)//枚举物品
    {
        for(int j = coins[i]; j <= amount; j++)//枚举背包
        {
            printf("i=%d, coins[%d]=%d, j=%d, dp[%d]=%d, j-coins[i]=%d\n", i, i, coins[i], j, j, dp[j], j-coins[i]);
            dp[j] += dp[j-coins[i]];
            printf("dp[%d]=%d\n", j, dp[j]);
        }
    }
    return dp[amount];
}

int main()
{
    int amount;
    int *coins;
    int coin_num;

    scanf("%d %d", &amount, &coin_num);
    if (amount == 0 || coin_num == 0 || coin_num > 300) {
        printf("input error:amount=%d, coin num=%d\n", amount, coin_num);
        return -1;
    }

    coins = malloc(sizeof(int) * coin_num);
    if (!coins) {
        printf("malloc failed\n");
        return -1;
    }

    for (int i = 0; i < coin_num; i++) {
        scanf("%d", &coins[i]);
    }

    int result = change(amount, coins, coin_num);
    printf("result:%d\n", result);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

3. 解决方案2

#include 
#include 

int dfs(int amount, int* coins, int coinsSize, int index, int sum){
    if (sum == amount) return 1;//找到一种方法，放回1

    if (sum > amount || index >= coinsSize) return 0;//超出边界或者无法组成，返回0

    int count = 0;
    //增加硬币索引
    count += dfs(amount, coins, coinsSize, index + 1, sum);
    //增加当前面额的计数
    count += dfs(amount, coins, coinsSize, index, sum + coins[index]);

    return count;
}

int main()
{
    int amount;
    int *coins;
    int coin_num;

    scanf("%d %d", &amount, &coin_num);
    if (amount == 0 || coin_num == 0 || coin_num > 300) {
        printf("input error:amount=%d, coin num=%d\n", amount, coin_num);
        return -1;
    }

    coins = malloc(sizeof(int) * coin_num);
    if (!coins) {
        printf("malloc failed\n");
        return -1;
    }

    for (int i = 0; i < coin_num; i++) {
        scanf("%d", &coins[i]);
    }

    int result = dfs(amount, coins, coin_num, 0, 0);
    printf("result:%d\n", result);

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

4. 本文解决方案参考

作者：_zhy
链接：https://leetcode.cn/problems/coin-change-ii/solutions/872055/liang-liao-4chong-fang-fa-3chong-tlenei-wk3xe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。