動態(tài)規(guī)劃的三要素:最優(yōu)子結(jié)構(gòu),邊界和狀態(tài)轉(zhuǎn)移函數(shù),最優(yōu)子結(jié)構(gòu)是指每個階段的最優(yōu)狀態(tài)可以從之前某個階段的某個或某些狀態(tài)直接得到(子問題的最優(yōu)解能夠決定這個問題的最優(yōu)解),邊界指的是問題最小子集的解(初始范圍),狀態(tài)轉(zhuǎn)移函數(shù)是指從一個階段向另一個階段過度的具體形式,描述的是兩個相鄰子問題之間的關系(遞推式)
成都創(chuàng)新互聯(lián)公司主營河北網(wǎng)站建設的網(wǎng)絡公司,主營網(wǎng)站建設方案,成都app軟件開發(fā)公司,河北h5小程序開發(fā)搭建,河北網(wǎng)站營銷推廣歡迎河北等地區(qū)企業(yè)咨詢
重疊子問題,對每個子問題只計算一次,然后將其計算的結(jié)果保存到一個表格中,每一次需要上一個子問題解時,進行調(diào)用,只要o(1)時間復雜度,準確的說,動態(tài)規(guī)劃是利用空間去換取時間的算法.
判斷是否可以利用動態(tài)規(guī)劃求解,第一個是判斷是否存在重疊子問題。
爬樓梯
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
注意：給定 n 是一個正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
1. ?1 階 + 1 階
2. ?2 階
示例 2：
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
1. ?1 階 + 1 階 + 1 階
2. ?1 階 + 2 階
3. ?2 階 + 1 階
分析:
假定n=10,首先考慮最后一步的情況,要么從第九級臺階再走一級到第十級,要么從第八級臺階走兩級到第十級,因而,要想到達第十級臺階,最后一步一定是從第八級或者第九級臺階開始.也就是說已知從地面到第八級臺階一共有X種走法,從地面到第九級臺階一共有Y種走法,那么從地面到第十級臺階一共有X+Y種走法.
即F(10)=F(9)+F(8)
分析到這里,動態(tài)規(guī)劃的三要素出來了.
邊界:F(1)=1,F(2)=2
最優(yōu)子結(jié)構(gòu):F(10)的最優(yōu)子結(jié)構(gòu)即F(9)和F(8)
狀態(tài)轉(zhuǎn)移函數(shù):F(n)=F(n-1)+F(n-2)
class Solution(object):
def climbStairs(self, n):
? ? """
? ? :type n: int
? ? :rtype: int
? ? """
? ? if n=2:
? ? ? ? return n
? ? a=1#邊界
? ? b=2#邊界
? ? temp=0
? ? for i in range(3,n+1):
? ? ? ? temp=a+b#狀態(tài)轉(zhuǎn)移
? ? ? ? a=b#最優(yōu)子結(jié)構(gòu)
? ? ? ? b=temp#最優(yōu)子結(jié)構(gòu)
? ? return temp
利用動態(tài)規(guī)劃的思想計算編輯距離。
編輯距離是指兩個字串之間，由一個轉(zhuǎn)成另一個所需的最少編輯操作次數(shù)。通常來說，編輯距離越小，兩個文本的相似性越大。這里的編輯操作主要包括三種：
插入：將一個字符插入某個字符串；
刪除：將字符串中的某個字符刪除；
替換：將字符串中的某個字符替換為另外一個字符。
那么，如何用Python計算編輯距離呢？我們可以從較為簡單的情況進行分析。
當兩個字符串都為空串，那么編輯距離為0；
當其中一個字符串為空串時，那么編輯距離為另一個非空字符串的長度；
當兩個字符串均為非空時(長度分別為 i 和 j )，取以下三種情況最小值即可：
1、長度分別為 i-1 和 j 的字符串的編輯距離已知，那么加1即可；
2、長度分別為 i 和 j-1 的字符串的編輯距離已知，那么加1即可；
3、長度分別為 i-1 和 j-1 的字符串的編輯距離已知，此時考慮兩種情況，若第i個字符和第j個字符不同，那么加1即可；如果相同，那么不需要加1。
很明顯，上述算法的思想即為 動態(tài)規(guī)劃 。
求長度為m和n的字符串的編輯距離，首先定義函數(shù)——edit(i, j)，它表示第一個長度為i的字符串與第二個長度為j的字符串之間的編輯距離。動態(tài)規(guī)劃表達式可以寫為：
if i == 0 且 j == 0，edit(i, j) = 0
if （i == 0 且 j 0 ）或者 （i 0 且j == 0），edit(i, j) = i + j
if i ≥ 1 且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + d(i, j) }，當?shù)谝粋€字符串的第i個字符不等于第二個字符串的第j個字符時，d(i, j) = 1；否則，d(i, j) = 0。
def edit_distance(word1, word2):
len1 = len(word1)
len2 = len(word2)
dp = np.zeros((len1 + 1,len2 + 1))
for i in range(len1 + 1):
? ? dp[i][0] = i? ?
for j in range(len2 + 1):
? ? dp[0][j] = j
for i in range(1, len1 + 1):
? ? for j in range(1, len2 + 1):
? ? ? ? delta = 0 if word1[i-1] == word2[j-1] else 1
? ? ? ? dp[i][j] = min(dp[i - 1][j - 1] + delta, min(dp[i-1][j] + 1, dp[i][j - 1] + 1))
return dp[len1][len2]
edit_distance('牛奶','華西奶')
結(jié)果：2
假設你正在爬樓梯。需要 n 階你才能到達樓頂。
每次你可以爬 1 或 2 個臺階。你有多少種不同的方法可以爬到樓頂呢？
注：n 是一個正整數(shù)。
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。
輸入： 3
輸出： 3
解釋： 有三種方法可以爬到樓頂。
在暴力法中，我們將會把所有可能爬的階數(shù)進行組合，也就是 1 和 2 。而在每一步中我們都會繼續(xù)調(diào)用 climbStairs，climbStairs 這個函數(shù)模擬爬 1 階和 2 階的情形，并返回兩個函數(shù)的返回值之和。
climbStairs(i,n) = climbStairs(i + 1, n) + climbStairs(i + 2, n)
其中 i 定義了當前階數(shù)，而 n 定義了目標階數(shù)。
在 n=5 時的遞歸樹將是這樣的：
在上一種方法中，我們計算每一步的結(jié)果時出現(xiàn)了冗余。另一種思路是，我們可以把每一步的結(jié)果存儲在 memory 數(shù)組之中，每當函數(shù)再次被調(diào)用，我們就直接從 memory 數(shù)組返回結(jié)果。
在 memory 數(shù)組的幫助下，我們得到了一個修復的遞歸樹，其大小減少到 n 。
不難發(fā)現(xiàn)，這個問題可以被分解為一些包含最優(yōu)子結(jié)構(gòu)的子問題，即它的最優(yōu)解可以從其子問題的最優(yōu)解來有效地構(gòu)建，我們可以使用動態(tài)規(guī)劃來解決這一問題。
第 ii 階可以由以下兩種方法得到：
在第 (i-1) 階后向上爬 1 階。
在第 (i-2) 階后向上爬 2 階。
所以到達第 i 階的方法總數(shù)就是到第 (i?1) 階和第 (i?2) 階的方法數(shù)之和。
令 dp[i] 表示能到達第 i 階的方法總數(shù)：
dp[i]=dp[i-1]+dp[i-2]
在上述方法中，我們使用 dp 數(shù)組，其中 dp[i]=dp[i-1]+dp[i-2]?？梢院苋菀淄ㄟ^分析得出 dp[i] 其實就是第 i 個斐波那契數(shù)。
Fib(n)=Fib(n-1)+Fib(n-2)
現(xiàn)在我們必須找出以 1 和 2 作為第一項和第二項的斐波那契數(shù)列中的第 n 個數(shù)，也就是說 Fib(1)=1 且 Fib(2)=2。
方法 5: Binets 方法
算法
這里有一種有趣的解法，它使用矩陣乘法來得到第 nn 個斐波那契數(shù)。矩陣形式如下：
令
按照此方法，第 nn 個斐波那契數(shù)可以由 Q n-1 [0,0] 給出。
讓我們試著證明一下。
我們可以使用數(shù)學歸納法來證明這一方法。易知，該矩陣給出了第 3 項（基本情況）的正確結(jié)果。由于
這證明基本情況是成立的。
假設此方法適用于查找第 nn 個斐波那契數(shù)，即 F n =Q n-1 [0,0]，那么：
現(xiàn)在，我們需要證明在上述兩個條件為真的情況下，該方法可以有效找出第 (n+1) 個斐波那契數(shù)，即，F(xiàn) n+1 =Q n [0,0]。
證明：
從而， F n+1 =Q n [0,0]。得證。
我們需要為我們的問題做的唯一改動就是將斐波那契數(shù)列的初始項修改為 2 和 1 來代替原來的 1 和 0 。或者，另一種方法是使用相同的初始矩陣 Q 并使用 result = Q n [0,0] 得出最后結(jié)果。發(fā)生這種情況的原因是我們必須使用原斐波那契數(shù)列的第 2 項和第 3 項作為初始項。
我們可以使用這一公式來找出第 n 個斐波那契數(shù)：
對于給定的問題，斐波那契序列將會被定義為 F 0 = 1，F(xiàn) 1 = 1，F(xiàn) 2 = 2，F(xiàn) n+2 = F n+1 + F n 。嘗試解決這一遞歸公式的標準方法是設出 F n ，其形式為 F n = a n 。然后，自然有 F n+1 = a n+1 和 F n+2 = a n+2 ，所以方程可以寫作 a n+2 = a n+1 + a n 。如果我們對整個方程進行約分，可以得到 a 2 = a + 1 或者寫成二次方程形式 a 2 - a- 1= 0。
對二次公式求解，我們得到:
一般解采用以下形式：
n = 0時，有A + B = 1
n = 1時，有
解上述等式，我們得到：
將 AA 和 BB 的這些值帶入上述的一般解方程中，可以得到：
共有2082876103種，其實這是一道典型的遞歸編程題，與其說是數(shù)學題，不如說是屬于計算機科學的范疇。
設f(n)表示n級臺階的爬法數(shù)目，則前幾個f值可以窮舉得f(1)=1，f(2)=2，f(3)=4。
n=4后，有如下遞歸關系：f(n)=f(n-1)+f(n-2)+f(n-3)，因為把爬n級臺階的最后一步分類，則f(n-1)代表最后一步是爬1級的所有走法，f(n-2)代表最后一步是爬2級的所有走法，f(n-3)代表最后一步是爬3級的所有走法，因此關系式成立。
用計算機迭代，得36級臺階的爬法數(shù)目為f(36)=2082876103種。
Matlab語言程序：
f=zeros(1,36);
f(1)=1; f(2)=2; f(3)=4;
for i=4:36
f(i)=f(i-1)+f(i-2)+f(i-3);
end
f(36)
如果想求解析解，可以考慮特征方程x^3=x^2+x+1的根為X，Y，Z，則數(shù)列的通解為
f(n)=A*X^n+B*Y^n+C*Z^n，通過f(1)，f(2)，f(3)的值，可以求出待定系數(shù)A，B和C。不過看來是挺麻煩的，因為特征方程的解是一個無理實數(shù)，和兩個共軛虛數(shù)。
可以看出來的是，該題可以用斐波那契數(shù)列解決。
樓梯一共有n層，每次只能走1層或者2層，而要走到最終的n層。不是從n-1或者就是n-2來的。
F(1) = 1
F(2) = 2
F(n) = F(n-1) + F(n-2) (n=3)
這是遞歸寫法，但是會導致棧溢出。在計算機中，函數(shù)的調(diào)用是通過棧進行實現(xiàn)的，如果遞歸調(diào)用的次數(shù)過多，就會導致棧溢出。
針對這種情況就要使用方法二，改成非遞歸函數(shù)。
將遞歸進行改寫，實現(xiàn)循環(huán)就不會導致棧溢出
爬樓梯
原題地址：
假設你正在爬樓梯，需要n步你才能到達頂部。但每次你只能爬一步或者兩步，你能有多少種不同的方法爬到樓頂部？
比如n=3，1+1+1=1+2=2+1=3，共有3種不同的方法
返回 3
這道題本質(zhì)上就是一道斐波那契數(shù)列的應用
假設一共有10階樓梯，每步可以爬1步或者2步，那么你爬到10階一共有兩種方法，從8階爬2步，或從9階爬1步，那么爬到9階也是這樣，那這就是一共基本的斐波那契數(shù)列。
遞歸算法
ted斐波那契數(shù)列：
還有一種快速求冪法：
假設你正在爬樓梯。需要 n?階你才能到達樓頂。每次你可以爬 1 或 2 個臺階。
注意：給定 n 是一個正整數(shù)。
示例 1：
輸入： 2
輸出： 2
解釋： 有兩種方法可以爬到樓頂。1 階 + 1 階 和 2 階
解題思路：
實現(xiàn)了兩種方法，但是第一種超出時間限制(?ì _ í?)，因為遞歸的時候方法實際計算了兩次。兩種方法都使用了動態(tài)規(guī)劃思想，比如對于爬10階樓梯，我們最后一步爬上第10階只會有兩種情況，一種是從9階樓梯爬1個臺階，一種是從8階臺階爬2兩個臺階上來。所以10階臺階問題可以劃分為爬9階和8階兩個子問題，一直遞歸劃分到只剩2階(2種方法)和1階(一種方法)。
超出時間限制的代碼：
class Solution:
def climbStairs(self, n: int) - int:
if n=2:
if n==2:
重慶分公司
重慶分公司
