演算法筆記系列 — 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
n
steps to reach the top.Each time you can either climb
1
or2
steps. In how many distinct ways can you climb to the top?
第一題是很經典的爬樓梯問題,當你一次只能走一步,或是走兩步的情況下,有多少種方式可以爬到 n 的階梯?
思考流程
我們先一個一個看,找出規律:
n = 1 (ans: 1)
1 step
n = 2 (ans: 2)
1 step + 1 step
2 steps
n = 3 (ans: 3)
1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step
n = 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
下去找也可以:
如果你覺得這篇文章對你有幫助,歡迎買杯咖啡贊助 ☕️ 謝謝