【第三轮】8.3-8.9 CareerCup 9.8

9.8 Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n
cents

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】
Reduce the original problem to sub-problems.
first use coins who have greater value  and the nuser coins with less value to make up the remaining value


【时间复杂度】
O(n)


【空间复杂度】
O(n)


【gist link】
https://gist.github.com/happyWinner/d1838f0faa48cc85c939

【解题思路】
1. recuision输出所有组合
2. only return number of ways of representations
--2.1 recursion
--2.2 DP keep track of results of the sub-problems
【时间复杂度】
O(N) - DP
【空间复杂度】
O(4N) - DP
【gist link】
https://gist.github.com/75356cc3be9d937e04d5


补充内容 (2014-8-17 09:17):
Thanks!! 本来想说这样更具体一点…lol

【解题思路】From the book
Use larger coins first
f(n):=
n > 25 f(n-25)+25 ...
【时间复杂度】
O(n)
【空间复杂度】
O(n)
【gist link】
https://gist.github.com/bitcpf/9ac3344682a848d8bf05

有人做过怎么把所有组合打出来的么?

有没有人能指点一下这道题的时间复杂度怎么估算出来的，对于这一章的时间复杂度计算都比较迷糊。难道都是用master theorem? 求大神指点一二