Leetcode硬币更换超时

Question

https://leetcode.com/problems/coin-change

以下输入得到超时，如果19-

[1,2,5]
19

// e.g. n === [1, 2, 5]
// e.g. t === target sum 
// c === counter, count each level
// h === hash, memo
var cc = function(n, t, c, h) {
    // index
    const index = t;
    // if we saw before, return it
    if(h[index]) {
        return h[index];
    }
    else if(t === 0) {
        // we use all the target, return the counter
        return c;
    }

    // mi === minimum counter
    let mi = Infinity;
    // e.g. we loop [1, 2, 5]
    for(let i=0; i<n.length; i++) {
        // only allow positive
        if(t-n[i] >= 0) {
            // recursive
            // mi === Infinity
            // t-n[i], consume it
            // c+1, increase the counter
            // h, pass down the hash
            mi = Math.min(mi, cc(n, t-n[i], c+1, h));
        }
    }

    // Update h[index] when mi < h[index]
    h[index] = mi < h[index] ? mi : h[index];
    return mi;
}


var coinChange = function(n, t) {
    const res = cc(n, t, 0, {});
    const out = res === Infinity ? -1 : res;
    return out;
};

有人知道哪里出了问题吗？

Answer 1

如果我们使用额外的内存来解决这个问题，也许会更容易：

const coinChange = function(coins, amount) {
    const inf = Math.pow(2, 31)
    const dp = []
    dp[0] = 0

    while (dp.length <= amount) {
        let curr = inf - 1
        for (let index = 0; index < coins.length; index++) {

            if (dp.length - coins[index] < 0) {
                continue
            }

            curr = Math.min(curr, 1 + dp[dp.length - coins[index]])
        }

        dp.push(curr)
    }

    return dp[amount] == inf - 1 ? -1 : dp[amount]
};

蟒蛇：

class Solution:
    def coinChange(self, coins, target):
        dp = [0] + [float('inf')] * target
        for index in range(1, target + 1):
            for coin in coins:
                if index - coin >= 0:
                    dp[index] = min(dp[index], dp[index - coin] + 1)
        
        return -1 if dp[-1] == float('inf') else dp[-1]

使用辅助函数（Java）：

class Solution {
    public int coinChange(int[] coins, int target) {
        if (target < 1)
            return 0;
        return helper(coins, target, new int[target]);
    }

    private int helper(int[] coins, int rem, int[] count) {
        if (rem < 0)
            return -1;
        if (rem == 0)
            return 0;
        if (count[rem - 1] != 0)
            return count[rem - 1];
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = helper(coins, rem - coin, count);
            if (res >= 0 && res < min)
                min = 1 + res;
        }

        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];

    }
}

• 有关更多详细信息，请参阅讨论板，在那里您可以找到大量解释良好的、使用多种语言的公认解决方案，包括低复杂度算法和渐进运行时/内存分析^1,2

Answer 2

以下是能够通过测试的案例。

修正了何时更新哈希

// keep it infinity or 0 or positive
h[index] = (h[index] === undefined ? mi : mi < h[index] ? mi : h[index]);

柜台只发生在功能区内。没有混在一起

result = cc(n, t-n[i], h)

var cc = function(n, t, h) {
    // index
    const index = t;
    // reach 0, re 0
    if(t === 0) {
        return 0;
    } else if(h[index] !== undefined) {
        // hash
        return h[index];
    }

    // min
    let mi = Infinity;
    // loop coin
    for(let i=0; i<n.length; i++) {
        // posi, get in
        if(t-n[i] >= 0) {
            // return count or hash
            mi = Math.min(mi, cc(n, t-n[i], h)+1);
        }
    }

    // keep it infinity or 0 or positive
    h[index] = (h[index] === undefined ? mi : mi < h[index] ? mi : h[index]);
    return h[index];
}


var coinChange = function(n, t) {
    const res = cc(n, t, {});
    const out = res === Infinity ? -1 : res;
    return out;
};

Answer 3

代码至少有一个问题。若要查看，请更改此行：

h[index] = mi < h[index] ? mi : h[index];

为此：

console.log(`Before: t: ${ t }, mi: ${ mi }, h[index]: ${ h[index] }`);
h[index] = mi < h[index] ? mi : h[index];
console.log(`After: t: ${ t }, mi: ${ mi }, h[index]: ${ h[index] }`);

并打电话：

console.log(coinChange([1,2,5], 3));

我认为，另一个问题是希望更新h[index]中记录的结果，但同时希望在我们进行更新之前返回其中存储的结果，两者之间存在差异。

想象一下，我们可以通过各种方式达到目标0，所以请考虑一下，如果第一个递归分支通过多个步骤的路径到达目标0，那么当前会发生什么。