動態規劃
刷題也有好幾個月了，但一直都是沉醉于陣列和字串這些入門的知識點，這假期準備好好啃一些知名的演算法了
動態規劃作為科技公司基本上必考的知識點，在刷題網站中占有很大的比重，很多的題目都可以用動態規劃去做，今天就來捋一捋dynamic program，
什么是動態規劃
先來個例題：
問總共有多少種方法可以走到右下角？
如果想用動態規劃解題，首先要先明確什么樣型別的題目適合用動態規劃去做，畢竟面試時
候，面試官不可能說：來用動態規劃給我解這道題，
動態規劃題目特點
**1**：計數
-計算有多少種方法走到右下角
-有多少種方法選出K個數使得和等于sum
**2**：求最值
-從左上角到右下角路徑的最大數值和‘
-最長上升子序列長度
**3**：求存在性
-取石子游戲，先手能否獲勝
-能否選出K個數使和為sum
實戰例題（LeetCode）
[LeetCode322](https://leetcode-cn.com/problems/coin-change/)
這就是一道典型的動態規劃的題目，因為題目要求最少的硬幣個數，但不是說所有的求最值都一定是動態規劃，
題目要求用最少的硬幣數，常規的思維也就是直覺一定是先盡量用較大的面額的硬幣，剩下的再用第二大，以此類推這樣一定是最少的，*但這樣一定是對的嗎？*來看個例子：
例如有2，5，7三種面額的硬幣，請你湊出27元，
所以直覺不一定是對的，動態規劃有固定的做題步奏，
一：確定狀態
動態規劃中確定狀態是最重要的事情，類似于確定陣列中a[i]代表著什么意義，
確定狀態需要兩個意識：
---- 最后一步
---- 子問題
**最后一步**：
就像LeetCode322題目中的一樣假設要湊的是用2,5,7湊27，雖然最開始不知道最優策略是
啥，但是可以明確的是肯定是K枚硬幣a1，a2............ak加一起和為27，
所以一定有一枚最后的硬幣ak，除去這個硬幣，其他的加一塊就是27-ak，
由上圖可以得知：我們不關心前K-1枚硬幣怎么拼出27-ak，可能有1種方法，也可能有1000000種，不care，但是可以確定的是 前面的確是拼出了27-ak，
再者，因為是最優策略，所以前K-1枚硬幣一定是最少的，
接下來的問題就是怎么用最少的硬幣拼出***27-ak***，
原問題是用最少的硬幣拼出 27.，將問題轉化為更小的規模了，為了簡化定義可以用f(x) = 最少用多少枚硬幣拼出x，
且最后一枚硬幣ak只可能是2，5，7中的一枚硬幣，如果ak=2，則 f(27)= f(27-2) + 1
，最后加一是加上最后一枚2塊錢的硬幣，其他的情況以此類推，
故可得出 f(27) = min { f(27-2)+1, f(27-5)+1, f(27-7)+1}
上式可理解成拼出27元所需的硬幣數目等于（拼出25所需的數目加一，拼出22所需的數目加一，拼出20所需的數目加一，三個中的最小值，）
二：轉移方程
**f(27) = min { f(27-2)+1, f(27-5)+1, f(27-7)+1}**
這就是實際code時候 ，也包括面試時候最重要的東西，寫對轉移方程基本上這題就做對一大半了，
三：邊界條件
刷過LeetCode或者牛客的人應該都有這種體驗，一道題能不能通過往往都是取決于那些坑爹的邊界條
件或者奇葩的測驗用例，
例如用2 3 5拼27那個例子，如果x-2 x-5 x-7小于0怎么辦，什么時候停下來？
所以f(1) = min { f(-1)+1, f(-4)+1, f(-6)+1} = 正無窮，表示拼不出來，
設定初始條件：f[0] = 0
四：計算順序
現在已經知道了轉移方程：f(X) = min { f(X-2)+1, f(X-5)+1, f(X-7)+1}
初始條件：f[0] = 0
計算順序從小到大，先計算f[1],f[2].......f[27].
從圖可以看出，從左往右計算，當計算拼出k的時候，需要分別用到前面的k減去前面三個面額硬幣的資料，
小結*
動態規劃的流程
1：確定狀態
-最后一步
-子問題
2：轉移方程
3：邊界條件
-陣列不可越界
-初始條件的設定‘
4：計算順序
-從左往右還是相反
BB了那么多，那道LeetCode還是沒做呢，322
talk is cheap，show me your code！
dp = [sys.maxsize-1] * (amount+1)#定義一個dp矩陣，分別存放著拼出dp[i]所需最少的硬幣個數
dp[0] = 0 #初始化dp矩陣最開始的元素為0
for i in range(amount+1):#初始化之后開始最dp陣列中每個元素進行賦值
if dp[i] == sys.maxsize - 1:#如果dp[i]當前元素為無窮，則說明此時無解，進行下輪回圈
continue
for coin in coins:#若此時dp[i]不是無窮大，則分別添加硬幣串列中的硬幣進行選擇
if coin + i <= amount:#如果加上此時的硬幣還小于amount
dp[i+coin] = min(dp[coin+i],dp[i]+1)#比較原始的跟加上一枚之后哪個更小
if dp[-1] == sys.maxsize -1:return -1#如果回圈賦值之后，dp[i]最后一位還是無窮，則無解
else:return dp[-1]#有解，則回傳最后一個數
覺得代碼注釋的可能不太清楚，靈魂畫手又手畫了一幅圖解釋代碼中的回圈都在干啥，覺得起碼這道題應該是解釋清楚了
還可以用遞回去解這道題，用字典去存盤每一步運算的結果這樣可以省掉多次重復運算，應該也是可以的！
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/252212.html
標籤：其他
下一篇：2021-01-24