如何找到给定目标数量所需的最少硬币数量（不同于现有的）

Question

这是一道经典题，在coins[]中给出了硬币数量的列表，len = coins[]数组的长度，我们试图找到最小数量的硬币需要获得 target.

硬币数组按升序排列

注意：我正在尝试优化效率。显然我可以通过硬币数组运行一个 for 循环并将 target%coins[i] 加在一起，但是当我有例如 coins[] = {1,3,4} 和 target = 6 时，这将是错误的，for 循环方法会给出3，也就是1,1,4，但是最优解是2，也就是3,3.

我还没有学过矩阵和多维数组，没有它们有没有办法做这道题？我写了一个函数，但它似乎在无限循环中运行ning。

int find_min(const int coins[], int len, int target) {
    int i;
    int min = target;
    int curr;
    for (i = 0; i < len; i++) {
        if (target == 0) {
            return 0;
        }
        if (coins[i] <= target) {
            curr = 1 + find_min(coins, len, target - coins[i]);
            if (curr < min) {
                min = curr;
            }
        }
    }
    return min;
}

Answer 1

我可以建议你阅读这篇文章，

https://www.geeksforgeeks.org/generate-a-combination-of-minimum-coins-that-results-to-a-given-value/

唯一就是没有C版的代码，如果真的需要可以自己移植

Answer 2

因为没有人给出好的答案，所以我自己想出来了。我不妨post一个答案。

我添加了一个名为lp的数组，在main中初始化，

int lp[4096];
int i;
    for (i = 0; i <= COINS_MAX_TARGET; i++) {
        lp[i] = -1;
    }

lp 的每个索引都等于-1。

int find_min(int tar, const int coins[], int len, int lp[])
{
    // Base case
    if (tar == 0) {
        lp[0] = 0;
        return 0;
    }

    if (lp[tar] != -1) {
        return lp[tar];
    }

    // Initialize result
    int result = COINS_MAX_TARGET;

    // Try every coin that is smaller than tar
    for (int i = 0; i < len; i++) {

        if (coins[i] <= tar) {

            int x  = find_min(tar - coins[i], coins, len, lp);

            if (x != COINS_MAX_TARGET)
                result = ((result > (1 + x)) ? (1+x) : result);
        }
    }

    lp[tar] = result;
    return result;
}

如何找到给定目标数量所需的最少硬币数量（不同于现有的）

How to find the minimum number of coins needed for a given target amount(different from existing ones)

c

dynamic-programming