本文素材來自視頻脱盲，請自備梯子觀看：What Is Dynamic Programming and How To Use It
Dynamic Programming：動(dòng)態(tài)規(guī)劃分為如下幾步：
- 將復(fù)雜問題拆分成多個(gè)較簡單的子問題
- 對每個(gè)子問題只計(jì)算一次镐捧，然后使用數(shù)據(jù)結(jié)構(gòu)（數(shù)組诈乒，字典等）在內(nèi)存中存儲(chǔ)計(jì)算結(jié)果
- 子問題的計(jì)算結(jié)果按照一定規(guī)則進(jìn)行排序（如郎哭，基于輸入?yún)?shù)）
- 當(dāng)需要再次運(yùn)算子問題時(shí)直接使用已存儲(chǔ)的計(jì)算結(jié)果而非再次運(yùn)算以提升求解性能
這種存儲(chǔ)計(jì)算結(jié)果以備再次使用稱之為：Memoization（這個(gè)詞，不知道怎么翻譯好）
以斐波那契數(shù)列為例來說明：
1驻呐、使用遞歸實(shí)現(xiàn)：
def fib(n):
if n < 1:
raise ValueError('參數(shù)n必須為大于0的整數(shù)')
if n == 1 or n == 2:
return 1
return fib(n-2)+fib(n-1)
這種方法是經(jīng)典的遞歸運(yùn)算碴犬。以fib(5)為例，整個(gè)求解過程可以拆分為：
圖片來自Youtube
我們可以看出按傅，fib(2)被計(jì)算三次捉超，fib(3)與fib(1)各被計(jì)算2次，時(shí)間復(fù)雜度為O(2^n)唯绍。
2拼岳、對遞歸進(jìn)行改進(jìn)
def fib_memory(n):
d = dict()
_fib_memory(n, d)
def _fib_memory(n, temp_dict):
if n < 1:
raise ValueError('參數(shù)n必須為大于0的整數(shù)')
if type(temp_dict) is not dict
raise TypeError('參數(shù)temp_dict必須為dict類型')
if n in temp_dict:
return temp_dict[n]
if n == 1 or n == 2:
result = 1
else:
result = fib_memory(n-1, temp_dict)+fib_memory(n-2, temp_dict)
temp_dict[n] = result
return result
圖片來自Youtube
優(yōu)化后，時(shí)間復(fù)雜度降為O(n)况芒。優(yōu)化后的算法依然使用了遞歸惜纸，當(dāng)參數(shù)較大時(shí)（如，1000）會(huì)導(dǎo)致棧溢出：
RecursionError: maximum recursion depth exceeded in comparison
3、脫離遞歸：
def fib_bottom_up(n):
l = [None]*(n+1)
return _fib_bottom_up(n, l)
def _fib_bottom_up(n, temp_list):
if n < 1:
raise ValueError('參數(shù)n必須為大于0的整數(shù)')
if type(temp_list) is not list:
raise TypeError('參數(shù)temp_list必須為list類型')
if temp_list[n] is not None:
return temp_list[n]
if n == 1 or n == 2:
return 1
temp_list[1] = 1
temp_list[2] = 1
for i in range(3, n+1):
temp_list[i] = temp_list[i-1]+temp_list[i-2]
return temp_list[n]
圖片來自Youtube
改進(jìn)之后的算法不再使用遞歸耐版，時(shí)間復(fù)雜度依然是O(n)祠够。
對以上三種實(shí)現(xiàn)編寫測試用例：
# coding=utf-8
import temp
import unittest
class TestDif(unittest.TestCase):
def test_fib_0_throw_value_error(self):
with self.assertRaises(ValueError):
temp.fib(0)
def test_fib_1_return_1(self):
result = temp.fib(1)
self.assertEqual(1, result)
def test_fib_10_return_false(self):
result = temp.fib(10)
self.assertFalse(result == 10)
def test_fib_memory_10_return_false(self):
result = temp.fib_memory(10)
self.assertNotEqual(result, 10)
def test_fib_bottom_up_1000_return_true(self):
result = temp.fib_bottom_up(1000)
print(result)
self.assertTrue(result > 100000)
if __name__ == "__main__":
unittest.main()
小結(jié)
無意中在Youtube上看到這段視頻，就翻譯整理下來與大家共享粪牲。
