Dynamic Programming

dynamic-programming ([DP) 是用來解多個重疊子問題所集合的問題，也常被使用找尋最佳路徑的問題。

dp最簡單可以使用 leetcode 的這題 509. Fibonacci Number 來試試看：

1. https://leetcode.com/problems/fibonacci-number/

通常DP的解答方式都是要尋找規律，直接從input/iuput觀察即可。通常沒有什麼領域涵意在裡面(不用太深究為什麼會有這樣個規律)

如何使用動態規劃(DP)

1. 70. Climbing Stairs (Easy)

這邊我們可以先觀察 只有一兩階的情況個是怎麼樣的結果，通常我會利用自訂測驗集來快速取得部分結果來觀察規律。

1 -> 1
2 -> 2
3 -> 3
4 -> 5 (1,1,1,1),(1,2,1),(2,1,1),(1,1,2),(2,2)
5 -> 8
6 -> 13

基本上確定好規律之後，我們就可以用上面的解法調整一下完成。

1. 152. Maximum Product Subarray

簡單來說，這題想要找的是最大乘積的子陣列。

思考流程

這題核心概念應該是，每回合的最大值是當下的最大值與目前值找最大的。

然而因為是乘積，當中又有負數，可能會讓上一個最小值(負數)立刻變成最大值。

因此，這邊每個階段的最小值的可能有

1. 當前數值
2. 前一個最小值*當前數值
3. 前一個最大值*當前數值

最大值則可能是

1. 當前數值
2. 前一個最小值*當前數值
3. 前一個最大值*當前數值

因此因們在這裡除了每次紀錄當下的最大值以外呢，也要同時紀錄當下的最小值，下一回合直接乘上負數。

所以回過頭來看看，我們切小的問題會是，每回合找最大值與最小值，而且最大最小值的找法為：

最大值：max (目前值、上一回合 max * 目前值、上一回合 min * 目前值)
最小值：min (目前值、上一回合 max * 目前值、上一回合 min * 目前值)

Reference

• [LeetCode] 583. Delete Operation for Two Strings 两个字符串的删除操作 https://www.cnblogs.com/grandyang/p/7144045.html
• 72. Edit Distance
• 1035. Uncrossed Lines
• 主要學習素材(大副份的內容都從這邊複製)