硬币改变

硬币改变(Coin Change)其实是动态规划里的组合问题,给出一个数 N ,在可选的数组S里 {s1,s2,s3...},有多少种组合的方式,使得它们的和等于 N。

其实就是固定总和求组合的可能数

N = 4
S = {1,2,3}
4种解决方案 {1,1,1,1},{1,1,2},{2,2},{1,3}

N = 10
S = {2, 5, 3, 6}
有 5 种 {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5}, {5,5}


算法分析

最优子结构(Optimal Substructure)

可以分解成2步

1.不包含某个数字

2.至少包含一次某个数字

此时我们可以设计一个函数 func(S, len, N) = func(S, len-1, N) + func(S, len, N - S[len-1])

重叠子问题(Overlapping Subproblems)

下面是递归实现此算法,子问题有重复计算

#include <stdio.h>

int conbination_sum(int *arr, int len, int sum)
{
    printf("{%d %d},", len, sum);
    // 和为0的组合有一种,即空组合
    if (sum == 0)
        return 1;
    
    // 和为负数,没有这种组合
    if (sum < 0)
        return 0;

    //数组为空,而和又是大于0,没有这种组合
    if (len <= 0 && sum >= 1)
        return 0;

    // 返回不包含最后一个数,或者至少包含一个最后一个数的所有组合的可能
    return conbination_sum(arr, len - 1, sum) + conbination_sum(arr, len, sum - arr[len-1]);
}

int main()
{
    int arr[] = {1,2,3};
    int len = sizeof(arr) / sizeof(int);
    printf("\nconbination sum: %d\n", conbination_sum(arr, len, 4));
    return 0;
}
{3 4},{2 4},{1 4},{0 4},{1 3},{0 3},{1 2},{0 2},{1 1},{0 1},{1 0},{2 2},
{1 2},{0 2},{1 1},{0 1},{1 0},{2 0},{3 1},{2 1},{1 1},{0 1},{1 0},{2 -1},{3 -2},
conbination sum: 4

从结果可以看出,很多相同的子问题都被计算了多次比如 1,1

跟其他动态规划问题一样,这里满足 最优子结构 和 重叠子问题,可以构建 arr[][]解决

下面是利用记忆法

#include <stdio.h>

int table[10][1024];

int conbination_sum(int *arr, int len, int sum)
{
    // 和为0的组合有一种,即空组合
    if (sum == 0)
        return 1;
    
    // 和为负数,没有这种组合
    if (sum < 0)
        return 0;

    //数组为空,而和又是大于0,没有这种组合
    if (len <= 0 && sum >= 1)
        return 0;

    if (table[len][sum])
        return table[len][sum] - 1;

    printf("{%d %d},", len, sum);

    // 返回不包含最后一个数,或者至少包含一个最后一个数的所有组合的可能
    int csum = conbination_sum(arr, len - 1, sum) + conbination_sum(arr, len, sum - arr[len-1]);
    
    table[len][sum] = csum + 1;
    return csum;
}

int main()
{
    int arr[] = {500,400,200};
    int len = sizeof(arr) / sizeof(int);
    printf("\nconbination sum: %d\n", conbination_sum(arr, len, 1000));
    return 0;
}


表格法-1

算法实现思路跟上面一样通过 1.不包含某个数   2.至少包含某个数   2种可能求解

#include <stdio.h>
#include <string.h>

int count( int S[], int m, int n ) 
{ 
    int i,j,x,y;

    int table[n+1][m];

    // 当和为0时,不管数组长度多少,都有一种可能(空组合)
    for (i = 0; i < m; i++) {
        table[0][i] = 1;
    }

    for (i = 1; i < n+1; i++) {
        for (j = 0; j < m; j++) {

            // 包含S[j]的可能组合数,如果S[j]比总和大,那么没有可能
            // 比如数组 {5} 组合成和 2 的所有可能为0
            x = S[j] > i ? 0 : table[i - S[j]][j];

            // 排除S[j]的可能组合数
            y = j >= 1 ? table[i][j-1] : 0;

            table[i][j] = x + y;
        }
    }

    return table[n][m-1];
}

int main()
{
    int arr[] = {2,5,3,6};
    int len = sizeof(arr) / sizeof(int);
    printf("\nconbination sum: %d\n", count(arr, len, 10));
    return 0;
}


表格法-2

这个实现发比上面有点抽象通过自底向上逐个元素累加的方式并记录和为特定值的可能组合数

以 {2,5,3,6} n=10为例,t[n] 代表和为 n 可能的组合数 

数组{2} t[2]=1(2)  t[4]=1(2,2)  t[6]=1(2,2,2) t[8]=1(2,2,2,2) t[10]=1(2,2,2,2,2)
数组{2,5},这里多了个 5,当 5 出现一次,那么需要前面存在t[5](不存在),当 5 出现2次,所以到这里t[10] = t[10] + (5,5) = 2
t[7] = t[2] + (5出现一次) = 1(给后面用)

数组 {2,5,3} 这里能和1个3组合成10需要t[7] = 1,2个3需要t[4],3个3不存在,即 t[10]=t[10]+t[7]+t[4]=4 (2,5,3)(2,2,3,3)
数组 {2,5,3,6} 这里6出现一次时,需要前面t[4]=1的次数即为当前组合的所有可能,当6出现2次时超过了10,所以不存在。
即 t[10] = t[10 + t[4] = 5(2,2,6)
所以一共有5种可能

下面是代码实现

#include <stdio.h>
#include <string.h>

int count( int S[], int m, int n ) 
{ 
    int table[n+1]; 
  
    memset(table, 0, sizeof(table)); 
    
    //空组合
    table[0] = 1; 
  
    for(int i=0; i<m; i++)
        for(int j=S[i]; j<=n; j++)
            table[j] += table[j-S[i]]; 
    return table[n]; 
} 

int main()
{
    int arr[] = {2, 5, 10};
    int len = sizeof(arr) / sizeof(int);
    printf("\nconbination sum: %d\n", count(arr, len, 10));
    return 0;
}


参考:

geeksforgeeks-coin-change-dp-7

上一篇: 最小路径开销
下一篇: 贪心算法
作者邮箱: 203328517@qq.com