如果面試題是求一個(gè)問題的最優(yōu)解（通常是求最大值或者最小值）曙求，而且該問題能夠分解成若干個(gè)子問題，并且子問題之間還有重疊的更小的子問題，就可以考慮用動(dòng)態(tài)規(guī)劃來解決這個(gè)問題聘鳞。
我們?cè)趹?yīng)用動(dòng)態(tài)規(guī)劃之前要分析能否把大問題分解成小問題，分解后的每個(gè)小問題也存在最優(yōu)解要拂。如果把小問題的最優(yōu)解組合起來能夠得到整個(gè)問題的最優(yōu)解抠璃，那么我們們可以應(yīng)用動(dòng)態(tài)規(guī)劃。
由于子問題在分解大問題的過程中重復(fù)出現(xiàn)脱惰，為了避免重復(fù)求解子問題搏嗡，我們可以用從下往上的順序先計(jì)算小問題的最優(yōu)解并存儲(chǔ)下來，再以此為基礎(chǔ)求取大問題的最優(yōu)解拉一。
動(dòng)態(tài)規(guī)劃求解問題的特點(diǎn)總結(jié)：
- 目標(biāo)是求一個(gè)問題的最優(yōu)解
- 整體問題的最優(yōu)解依賴于各個(gè)子問題的最優(yōu)解
- 我們把大問題分解成若干小問題采盒，這些小問題之間還有相互重疊的更小的問題
- 從上往下分析問題，從下往上求解問題
貪婪算法和動(dòng)態(tài)規(guī)劃不一樣蔚润。當(dāng)我們應(yīng)用貪婪算法解決問題的時(shí)候磅氨，每一步都可以做出一個(gè)貪婪的選擇，基于這個(gè)選擇嫡纠，我們確定能夠得到最優(yōu)解烦租。
題目：給你一根長(zhǎng)度為n的繩子，請(qǐng)把繩子剪成m段（m除盏、n都是整數(shù)叉橱，n>1并且m>1），每段繩子的長(zhǎng)度記為k[0],k[1],...,k[m]痴颊。請(qǐng)問k[0]*k[1]*....*k[m]可能的最大乘積是多少赏迟？
-
動(dòng)態(tài)規(guī)劃
class Solution: def max_product_afer_cut(self, length): # 如果特殊長(zhǎng)度的繩子 if length < 2: return 0 if length == 2: return 1 if length == 3: return 2 products = [None] * (length + 1) # 如果繩子中有長(zhǎng)度為1， 2蠢棱， 3的段锌杀，不用去分剪它們 products[:4] = (0, 1, 2, 3) _max = 0 # 開始從下往上遍歷求出每個(gè)小段的最大乘積 for i in range(4, length+1): _max = 0 for j in range(1, i//2 + 1): pro = products[j] * products[i-j] if _max < pro: _max = pro products[i] = _max _max = products[length] return _max -
貪婪算法
class Solution: def max_product_after_cut(self, length): # 特殊長(zhǎng)度的繩子 if length < 2: return 0 if length == 2: return 1 if length == 3: return 2 times_of_three = length // 3 if (length - times_of_three * 3) == 1: times_of_three -= 1 times_of_two = length - times_of_three * 3 return pow(3, times_of_three) * pow(2, times_of_two)?
