Q1. 動態規劃(Dynamic Programming)是什麼 ?

• Dynamic programming，簡稱DP，是一種多階段決策出最佳解的方法，他會將問題分成子問題、子子問題...，拆成多個子問題進行求解，並且求出最佳解

• DP 可以大致理解為是分治法 + 記憶法

  • 首先定義出將大問題切割為子問題的方法。
  • 當一個子問題的答案被計算出來後，採取記憶法，將答案儲存在記憶體中，避免未來重複計算。

• 以計算費氏數列為例：
  

• 計算 f(5)：
  

• 可以看到圖中綠色的數字都會重複計算，而隨著 n 越大，重複計算的會越多。

• 此時可以將計算過的答案保存在記憶體中，用空間換取時間，大幅節省效能。

參考資料：https://www.gushiciku.cn/pl/pKW7/zh-tw

參考資料：https://codertw.com/程式語言/586675/

Q2. 學會 動態規劃概念可以做什麼 ?

• 動態規劃問題在程式競技比賽中，是經典的問題，常見的問題有：
  • 背包問題
  • 最佳二分搜尋樹
  • 切割鋼條問題
    
    參考資料：https://zhuanlan.zhihu.com/p/368171848

Lab. 明天要解的題目：53. Maximum Subarray

• 題目敘述：https://leetcode.com/problems/maximum-subarray/

• 題目敘述：

  • 題目會給一個 nums 的 list，需要找出至少一個數字的連續值，他們相加的結果會是最大的

  

• 測資的 Input/Output

  • 會給一個 nums 的 list，需要回傳連續相加最大的值
    

• 題目的條件

  • list 長度在 1~30000 間
  • 每個值借於 -100000 ~ 100000 間
    

• 看完題目，你要思考：

  • 你是否把每個 list 值相加結果儲存起來?
  • 你是否能不使用額外使用 list 空間解決這一題?
  • 什麼算法可以不造成超時?