首页 > 代码库 > 找钱方式:递归,循环的解法

找钱方式:递归,循环的解法

题目:给定一个金额m,以及几种钱币面值(比如1,2,5),求m有多少种找钱方式

解答:

a(m, c): 金额m的找钱方式,此时最大钱币面值为c

a(m, c) = sigma( a(m - k*c, next_c) ); k=0~m/c, next_c=比c小的下一个面值的钱币,比如c=5, next_c = 2

按照以上递推式,可以写出递归函数

int exchangeWays(int money, int maxCurIndex = currencyNum - 1)
{
    if (money == 0) return 1;
    if (maxCurIndex == -1) return 0;
    int ways = 0;
    int maxCur = currency[maxCurIndex];
    for (int i = 0; i * maxCur <= money; i++)
        ways += exchangeWays(money - i * maxCur, maxCurIndex - 1);
    return ways;
}
这种解法的复杂度很高,O(m^(c的个数))


循环解法1

有几个c就有几层循环,复杂度也是O(m^(c的个数))

int exchangeWaysIter(int money)
{
    int ways = 0;
    for (int i = 0; i * currency[2] <= money; i++)
    {
        money -= i * currency[2];
        for (int j = 0; j * currency[1] <= money ; j++)
        {
            money -= j * currency[1];
            for (int k = 0; k * currency[0] <= money; k++)//if currency[0] is 1, we can delete this loop
            {
                if (money == k * currency[0])
                    ++ways;
            }
            money += j * currency[1];
        }
        money += i * currency[2];
    }
    return ways;
}

重新观察递推式,我们可以得出循环解法2

int exchangeWaysIter2(int money)
{
    vector<int> ways(money + 1);//ways(i) : sum equals i, exchange ways
    ways[0] = 1;
    for (int i = 0; i < currencyNum; i++)
    {
        for (int j = 0; j + currency[i] <= money; j++)
        {
            if (ways[j])
                ways[j + currency[i]] += ways[j];
        }
    }
    return ways[money];
}
时间复杂度为O(m*(c的个数)),空间复杂度为O(m)

一下就降低了时间复杂度。


找钱方式:递归,循环的解法