演算法筆記系列 — Dynamic programming 動態規劃
Dynamic Programming 動態規劃，通常會簡稱作為 DP，是一個在解題很常用的一種解題方式，原理是透過把原問題分解為相對簡單的子問題的方式，來求解複雜問題的方法。
什麼是動態規劃？
動態規劃在尋找有很多重疊子問題的情況的最佳解時有效，當遇到複雜的計算且有規律的問題時，我們可以使用動態規劃來將問題分解成數個小問題，找到其中的規律，每次將小問題的答案記錄下來，當下一回來用到前一回合答案時就直接查表，也可以說是一種用空間換取時間的解題方式。
Fibonacci number
費氏數列可以當一個最簡單的例子，讓我們暸解到底什麼是動態規劃。
在數學上，我們知道費氏數列的定義如以下所示：
也就是在 Fn 的時候，他的值會是前一個 Fn-1 與前前一個 Fn-2 相加的結果，寫成程式碼的話可以很直覺就是使用遞迴，可以很簡單的寫出：
那接著我們來用 Dynamic Programming 的方式來思考一下：
- 費氏數列很明顯地是由多個重疊子問題所集合的問題
- 可以很容易地找出當中的規律
因此，我們改成將每回合的結果都記錄下來，使用查表的方式來實作：
兩者的執行速度，DP 的方式會比遞迴方式還要快一些些，可以使用 leetcode 的這題 509. Fibonacci Number 來試試看：(P.S. leetcode 上的執行時間不一定完全準確就是了，可以當參考用)
實際上如何應用？
其實動態規劃的核心概念不難理解，比較難的是如何從題目裡看出要使用以及如何使用動態規劃，來分解一個複雜的問題，這裡就分別各挑一題 Easy 與 Medium 的問題來使用 DP 解題。
70. Climbing Stairs (Easy)
You are climbing a staircase. It takes
nsteps to reach the top.Each time you can either climb
1or2steps. In how many distinct ways can you climb to the top?
第一題是很經典的爬樓梯問題，當你一次只能走一步，或是走兩步的情況下，有多少種方式可以爬到 n 的階梯？
思考流程
我們先一個一個看，找出規律：
n = 1 (ans: 1)
1 stepn = 2 (ans: 2)
1 step + 1 step
2 stepsn = 3 (ans: 3)
1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 stepn = 4 (ans: 5)
1 step + 1 step + 1 step + 1 step
1 step + 1 step + 2 steps
1 step + 2 steps + 1 step
2 steps + 1 step + 1 step
2 steps + 2 steps大概到這裡就可以看出這個爬樓梯問題其實就是一個費式數列，其規律會是 Fn = Fn-1 + Fn-2 。
152. Maximum Product Subarray
Given an integer array
nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
簡單來說，這題想要找的是最大乘積的子陣列。
思考流程
這題核心概念應該是，每回合的最大值是當下的最大值與目前值找最大的。然而因為是乘積，當中又有負數會來攪局，如果前一回合是一個負很大值，這回合再乘上一個複數，馬上就風雲變色直接變成最大了。
因此，我們在這裡除了每次紀錄當下的最大值以外呢，也要同時紀錄當下的最小值，以免下一回合直接乘上負數。
所以回過頭來看看，我們切小的問題會是，每回合找最大值與最小值，而且最大最小值的找法為：
- 最大值：max (目前值、上一回合 max * 目前值、上一回合 min * 目前值)
- 最小值：min (目前值、上一回合 max * 目前值、上一回合 min * 目前值)
這裡就會需要分別一個紀錄 max 與 min 的表，每回合我們只需要查表找出上一回合的最大最小值，並且更新這回合的值，最後就可以找到答案了！
更多題目
其他可以使用DP的題目：
或是直接從這個 tag 下去找也可以：
如果你覺得這篇文章對你有幫助，歡迎買杯咖啡贊助 ☕️ 謝謝
