首页 文章

为什么我的解决方案leetcode 322 Coin Change超时

提问于
浏览 次
-3

这是我的代码：

class Solution {
    std::unordered_map<int, int> um;
public:
    int coinChange(vector<int>& coins, int amount) {
        if (amount == 0)
            return 0;

        auto it = um.find(amount);
        if (it != um.end())
            return it->second;

        int ret = -1;

        for (int c : coins)
        {
            int n = 1;
            while (true)
            {
                int a = amount - n * c, m = 0;
                if (a < 0)
                    break;
                if (a > 0)
                    m = coinChange(coins, a);
                if (m != -1)
                {
                    if (ret == -1)
                        ret = m + n;
                    else
                        ret = std::min(ret, m + n);
                }
                n++;
            }
        }

        um[amount] = ret;
        return ret;
    }
};

据我所知，它与最受欢迎的解决方案非常相似，它甚至构造了相同的哈希表 . 但是我在任意输入时都会超时 . 我无法在本地找到任何错误 .

什么想法可能是错的？

编辑：

我包括问题陈述：

您将获得不同面额的硬币和总金额 . 编写一个函数来计算构成该数量所需的最少数量的硬币 . 如果这笔钱不能由任何硬币组合弥补，则返回-1 .

示例：coins = [1,2,5]，金额= 11返回3（11 = 5 5 1）

该方法：

使用动态编程（递归记忆） . 对于金额，只要金额是正数，就尝试每一枚硬币 . 对于上面的例子：

S(11) = 1 + S(10) | 2 + S(9) | 3 + S(8) | ... | 11 + S(0) | //try coin 1

        1 + S(9) | 2 + S(7) | 3 + S(5) | ... | 5 + S(1) | //try coin 2

        1 + S(6) | 2 + S(1) //try coin 5

请原谅这个问题的混乱，我相信我对上述想法的实现有一些错误，但我很难找到它 .

c++ algorithm

1 回答

  • 0

    Later edit: I was wrong

    我注意到C版本的运行时间仍然太高，所以这不是问题 . 我设法从Leetcode获得所有测试并发现了问题 .

    对于测试案例硬币：{3,7,405,436}和金额：8839我的实施将拨打18744855电话，而最受欢迎的只有34486 .

    这是因为，对于每个硬币，我尝试尽可能多地将其放入数量（ while (true) 循环），并且在每次尝试之后我进行递归调用 . 它是这样的（对于coin = {1}和amount = 3）：

    S(3) = min{1 + S(2), 2 + S(1), 3 + S(0)}

S(2) = min{1 + S(1), 2 + S(0)}

S(1) = min{1 + S(0)}

S(0) = 0

    然而，只需尝试一次硬币并让递归调用处理剩下的就足够了，就像流行的解决方案一样：

    S(3) = min{1 + S(2)}

S(2) = min{1 + S(1)}

S(1) = min{1 + S(0)}

S(0) = 0

    Previous answer:

    我已经将相同的解决方案移植到C，并且已被接受，因此我认为这是Leetcode基础结构中的一些问题 .

    int coinChange_(int* coins, int coinsSize, int *um, int amount) {
    if (amount == 0)
        return 0;

    if (um[amount] != 0)
        return um[amount];

    int ret = -1;

    for (int i = 0; i < coinsSize; i++)
    {
        int c = coins[i];
        int n = 1;
        while (true)
        {
            int a = amount - n * c, m = 0;
            if (a < 0)
                break;
            if (a > 0)
                m = coinChange_(coins, coinsSize, um, a);
            if (m != -1)
            {
                if (ret == -1)
                    ret = m + n;
                else
                    ret = m + n < ret ? m + n : ret;
            }
            n++;
        }
    }

    um[amount] = ret;
    return ret;
}

int coinChange(int* coins, int coinsSize, int amount) {
    int *um = calloc(amount + 1, sizeof *um);
    int ret = coinChange_(coins, coinsSize, um, amount);
    free(um);
    return ret;
}
    回复于

相关问题