摘要：平時練習算法題學習算法知識時，經常會發現題解裡寫着“動态規劃”，裡面一上來就是一個複雜的dp公式，對于新人來說除了說聲“妙啊”，剩下就是疑惑，他是怎麼想到這個公式的？我能想到嗎？這玩意工作中有用嗎？
本文分享自華為雲社群《動态規劃究竟是怎麼想到的？【奔跑吧！JAVA】》，原文作者：breakDraw。
平時練習算法題學習算法知識時，經常會發現題解裡寫着“動态規劃”，裡面一上來就是一個複雜的dp公式，對于新人來說除了說聲
剩下就是疑惑，他是怎麼想到這個公式的？我能想到嗎？這玩意工作中有用嗎？
加上“動态規劃”這高端的名字，然後就勸退了不少試圖去了解他的人。
動态規劃聽起來太吓人，可以換個說法
我在内心更喜歡叫他“狀态緩存”
如果是服務開發，相信很熟悉這個詞語， 利用緩存來加快一些重複的請求的響應速度。
而這個緩存的特點是 和其他緩存有所關聯。
比如我們的服務要計算7天内的某金錢總和，計算後要緩存一下。
後來又收到一個請求，要計算8天内的金錢總和
那我們隻需要取之前算過的7天内的金錢綜合，加上第8天的金錢就行了。
1+4的思考套路
自己針對動态規劃總結了一個自己的思考套路，我叫他1組例子4個問題，就叫1+4好了，通過這5個過程，可以站在普通人的角度（就是非acm大佬那種的角度），去了解動态規劃是如何被思考出來的
- 在逾時的思路上寫出一組計算過程的例子
- 在逾時例子的基礎上，有哪些重複、浪費的地方？
- 如何定義dp數組
- 狀态的變化方向是什麼，是怎麼變化的
- 邊界狀态是什麼
簡單例子
以一道簡單題為例：
爬樓梯：
https://leetcode-cn.com/problems/climbing-stairs/
這時候就要靜下心，觀察這個解法的例子中是否有重複經曆的場景，而這個重複經曆的場景就叫狀态。
我處理動态規劃的題目時， 都會問自己3個問題，一般就能順利地解決。
①在逾時的思路上寫出一組計算過程的例子
如果我們考慮最簡單的解法， 就是從起點開始，每次選擇走1步或者走2步，看下能否走到終點，能走到則方法數+1。
但這種方法注定逾時（O（n^2)）
但我還是照着這個過程模拟了一下，随便列了幾個
1 ->2-> 3-> 4-> 5
1 ->2 ->3-> 5
1->3->4->5
1->3->5
②在逾時例子的基礎上，有哪些重複、浪費的地方？
在上面，我發現了重複的地方
也就是說
從3到5總共就2種路線，已經在1->2之後計算過了，我後面從1走到3再往後走時，沒必要再去算了。
換言之，當我走到3的時候，其實早就可以知道後面還剩下多少種走法。
發現重複的地方後，就可以開始建立dp公式了。
③如何定義dp數組？
定義dp數組，也就是定義上面提到的重複的地方。重新看下之前的那句話
當我走到3的時候，其實早就可以知道後面還剩下多少種走法。
是以dp[3]代表的就是從3往後，有多少種可走的方法。
④狀态的變化方向是什麼，是怎麼變化的
-
首先思考狀态的變化方向
重新看這句話：
當我走到3的時候，其實早就可以知道後面還剩下多少種走法
說明結果取決于往 後面 的狀态
是以我們要先計算後面的狀态, 即從後往前算
- 接着思考這個後面的狀态和目前的狀态有什麼聯系，是怎麼變化的
這個一般都包含在題目條件中
根據題意，要麼走2步，要麼走1步，是以每當我走到一層時，下一次就2種狀态可以變化。
那麼對于第3層而言，他後續有2種走法，走1步或者走2步
那麼他的情況就是dp[3] = dp[3+1] + dp{3+2}
如果層數設為i，那麼這個變化情況就是
dp[i] = dp[i+1] + dp[i+2]
⑤邊界狀态是什麼？
邊界狀态就是不需要依賴後面的狀态了，直接可以得到結果的狀态。
在這裡肯定就是最後一層dp[n]， 最後一層預設是一種走法。 dp[n]=1
實作
根據上面的過程，自己便定義了這個狀态和變化
- 定義：dp[i] : 代表從第i層往後，有多少種走法
- 方向和變化：dp[i] = dp[i+1] + dp[i+2];
-
邊界: dp[n] = 1
根據這個寫代碼就很容易了
代碼：
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[n] = 1;
dp[n-1] = 1;
for(int i = n-2; i >=0;i--) {
dp[i] = dp[i+1] + dp[i+2];
}
return dp[0];
} 進階版，二維的動态規劃
https://leetcode-cn.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/
逾時的思路肯定是像搜尋一樣模拟所有的行走過程。
先假設1個steps=5, arrlen=3的情況
随便先列幾個。模拟一下不斷走的位置。數字指的是目前位置。
0->1->2->1->0->0
0->1->2->1->1->0
0->1->1->1->1->0
0->1->1->1->0->0
0->0->1->1->1->0
……
0->0->1->1->0->0
我發現這部分标粗的部分重複了，
換句話說
當我還剩2步且目前位置為1的時候，後面還有多少種走法，其實早就知道了。
涉及了2個關鍵因素: 剩餘步數和目前值，是以得用二維數組
是以
dp[realstep][index]
就代表了 剩餘步數為step且位置為index時， 後續還剩多少種走法。
- 先思考變化方向
“當我還剩2步且目前位置為1的時候，後面 還有多少種走法，其實早就知道了。”
這個後面是指啥， 後面會怎麼變?
後面肯定是步數越來越少的情況， 并且位置會根據規律變化。 是以變化方向是步數變少，位置則按照規定去變。
那麼這個固定越來越少的這個“剩餘步數”，就是核心的變化方向。
我們計算時，可以先計算小的剩餘步數的狀态， 再去算大的剩餘步數。
- 如何變化
根據題意和方向，剩餘步數肯定-1， 然後位置有3種選擇（減1，不變，加1）， 那麼方法就是3種選擇的相加。
dp[step][index] = dp[step-1][index-1] + dp[step-1][index] + dp[step-1][index+1]
剩餘步數為0時，隻有目前位置為0才是我們最終想要的方案，把值設為1并提供給後面用，其他位置且步數為0時都認為是0。
dp[0][0] = 1；
dp[0][index] = 0；（index>0)
那麼最終出來了
- 定義：dp{realstep][index]: 剩餘步數為step且位置為index時， 後續還剩多少種走法。
- 方向和變化：dp[step][index] = dp[step-1][index-1] + dp[step-1][index] + dp[step-1][index+1]
- 邊界: dp[0][0] = 1；
記憶體溢出處理
不過這題因為是困難題，是以給上面這個公式設立了一個小難度：
數組長度非常大，導緻如果index的範圍我們選擇為0~arrLen-1, 那麼最大情況dp[500][10^6]注定逾時記憶體範圍。
這時候就要去思考index設那麼大是不是沒必要
一般我們可以自己列這種情況的小例子，例如
step=2, arr=10
然後看下index有沒有必要設成0~9，随便走幾步
0->1->0
0->0->0
嗯？我發現就3種情況，arr後面那麼長不用啦？
于是發現規律：
剩餘的步數，必須支撐他傳回原點！
也就是說，其實index的最大範圍最多就是step/2， 不能再多了，再多肯定回不去了。
于是問題解決。
其他類似題目練習
https://leetcode-cn.com/problems/minimum-cost-for-tickets/
點選關注，第一時間了解華為雲新鮮技術~