首页 > 代码库 > 找钱方式:递归,循环的解法
找钱方式:递归,循环的解法
题目:给定一个金额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)
一下就降低了时间复杂度。
找钱方式:递归,循环的解法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。