斐波那契數(shù)列
斐波那契額數(shù)列：1,1,2,3,5,8,13,21,34
設(shè)計(jì)一個(gè)函數(shù)，求第n位上的數(shù)括享。
1.暴力解 很簡(jiǎn)單的方法：
def fib(n):
if n == 1 or n == 2:
return 1
else:
return fib(n - 1) + fib(n - 2)
但是搂根，這個(gè)方法有一個(gè)很大的問(wèn)題，計(jì)算重復(fù)太多铃辖，例如剩愧，我們要算fib(5)
- fib(5)
- fib(4)
- fib(3)
- fib(2)
- fib(1)
- fib(2)
- fib(3)
- fib(3)
- fib(2)
- fib(1)
- fib(4)
2.DP algorithm
可以發(fā)現(xiàn)，當(dāng)中有大量的重復(fù)計(jì)算娇斩。我們可以設(shè)計(jì)一個(gè)備忘錄仁卷，將算過(guò)的數(shù)值保存進(jìn)去。
dic = {}
def fib2(n):
if n in dic:
return dic[n]
if n == 0:
return 0
if n == 1:
return 1
value = fib2(n - 1) + fib2(n - 2)
dic[n] = value
return value
3.自下而上的DP algorithm
或者犬第，從下而上進(jìn)行動(dòng)態(tài)規(guī)劃
dp = []
def fib3(n):
dp = [0] * (n + 1)
if n == 0:
return 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
比較fib(40),三種方法的時(shí)間分別是
27.43297505378723
3.62396240234375e-05
1.5020370483398438e-05
我們發(fā)現(xiàn)锦积，時(shí)間成指數(shù)下降
我們發(fā)現(xiàn)，其實(shí)瓶殃，f(n) 只和前兩個(gè)數(shù)字有關(guān)充包，所以，第三種方法沒(méi)有必要設(shè)置一個(gè)n+1長(zhǎng)的盒子來(lái)保存數(shù)字遥椿，將fib3優(yōu)化：
def fib4(n):
if n == 2 or n == 1:
return 1
prev = 1
curr = 1
for i in range(3, n + 1):
sum = prev + curr
prev = curr
curr = sum
return curr
時(shí)間進(jìn)一步降低：
6.9141387939453125e-06
找零錢
找零錢問(wèn)題基矮，給一個(gè)零錢數(shù)列:[1,2,5]，現(xiàn)在如果有11塊錢冠场，問(wèn)最少幾枚硬幣能湊出這個(gè)數(shù)額家浇。
1.暴力解
如果要湊11，那么如果知道怎么湊10碴裙，就知道怎么湊11钢悲，因?yàn)橛?0，再加上一枚硬幣就可以得到11舔株。
遞歸樹(shù)
但是需要選擇硬幣最少的那個(gè)結(jié)果：
def coinChange(amount):
if amount == 0:
return 0
if amount < 0:
return -1
res = float('INF')
for coin in coins:
subproblem = coinChange(amount - coin)
if subproblem == -1: continue
# choose the min because we need the best choose, least coins --> minimum amount
res = min(res, 1 + subproblem)
return res if res != float('INF') else -1
2.DP algorithm
同上面斐波那契數(shù)列一樣莺琳，列一個(gè)備忘錄(memo)
memo = {}
def coinChange2(amount):
if amount in memo:
return memo[amount]
if amount == 0:
return 0
if amount < 0:
return -1
res = float('INF')
for coin in coins:
subproblem = coinChange(amount - coin)
if subproblem == -1: continue
res = min(res, 1 + subproblem)
memo[res] = res if res != float('INF') else -1
return memo[res]
3.自下而上的DP algorithm
def coinChange3(amount):
dp = [amount + 1] * (amount + 1)
dp[0] = 0
for item in range(len(dp)):
for coin in coins:
if (item - coin < 0): continue
dp[item] = min(dp[item], 1 + dp[item - coin])
print(dp)
return -1 if (dp[amount] == (amount + 1)) else dp[amount]
可以發(fā)現(xiàn)，每一次的結(jié)果：
[0, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 2, 12, 12, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 1, 12, 12, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 1, 2, 12, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 1, 2, 12, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 1, 2, 3, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 1, 2, 2, 12, 12, 12, 12, 12, 12, 12]
[0, 1, 1, 2, 2, 3, 12, 12, 12, 12, 12, 12]
[0, 1, 1, 2, 2, 3, 12, 12, 12, 12, 12, 12]
[0, 1, 1, 2, 2, 1, 12, 12, 12, 12, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 12, 12, 12, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 12, 12, 12, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 12, 12, 12, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 3, 12, 12, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 12, 12, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 12, 12, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 12, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 12, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 12, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 4, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 12, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 4, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 4, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 12]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
[0, 1, 1, 2, 2, 1, 2, 2, 3, 3, 2, 3]
dynamic programming 就是一種聰明的窮舉
