最小硬币，无DP

Question

public int MinCoins(int[] change, int cents)
{
    Stopwatch sw = Stopwatch.StartNew();

    int coins = 0;
    int cent = 0;
    int finalCount = cents;
    for (int i = change.Length - 1; i >= 0; i--)
    {
        cent = cents;

        for (int j = i; j <= change.Length - 1; j++)
        {
            coins += cent / change[j];
            cent = cent % change[j];
            if (cent == 0) break;
        }

        if (coins < finalCount)
        {
            finalCount = coins;
        }
        coins = 0;
    }
    sw.Stop();
    var elapsedMs = sw.Elapsed.ToString(); ;
    Console.WriteLine("time for non dp " + elapsedMs);
    return finalCount;
}

public  int MinCoinsDp(int[] change, int cents)
{
    Stopwatch sw = Stopwatch.StartNew();
    int[] minCoins = new int[cents + 1];

    for (int i = 1; i <= cents; i++)
    {
        minCoins[i] = 99999;

        for (int j = 0; j < change.Length; j++)
        {

            if(i >= change[j])
            {

                int n = minCoins[i - change[j]] + 1;

                if (n < minCoins[i])
                    minCoins[i] = n;
            }
        }
    }
    sw.Stop();
    var elapsedMs = sw.Elapsed.ToString();
    Console.WriteLine("time for dp " + elapsedMs);

    return minCoins[cents];
}

我已经使用迭代和动态编程编写了最少数量的硬币程序。我看过很多博客讨论DP来解决这个问题。迭代解的运行时间为O(numberOfCoins * numberofCoins)，DP的运行时间为O(numberofcoins running *arraySize)。哪一个更好？请推荐一本高级算法的好书。

请使用{v1 > v2 > v3 > v4}运行，如{25,10,5}

Answer 1

我看到您正在尝试测量这两种算法的运行时间，并决定哪一种更好。

关于你的算法，还有一件更重要的事情。不幸的是，第一个是不正确的。例如，请考虑以下输入：

假设我们想要交换100，并且可用硬币具有以下名义形式：5, 6, 90, 96。我们能做的最好的事情就是使用3硬币：5, 5, 90。但是，您的解决方案将返回1