dynamicProgram.md

動態規劃

• example
  • 給定矩陣、幾人從左上到右下，每次只能往下或往右，求有多少種方式可以走到終點？
  • 如何得知要用動態規劃？
    1. 求方式數：how many ways...
    2. 求最大最小值：例如本題改為：求哪個路徑的數字和最大 or 最小，或是給定一個數字 list，求最長 or 最短的升冪 list 。maximum minimum...
    3. 求可行性：問題通常是問是 or 否。例如撿石頭遊戲，兩人輪流拿，先拿的人是不是必勝？給定一個數列，判斷是否能選出 k 個數使得和為 total
  • 小試身手：https://leetcode.com/problems/coin-change/
  • 動態規劃五步驟：
    1. 確定狀態：通常都要開一個 list (array)，無論是一維還是二維，這個 array 中的 array[i][j] 代表著某個情形下的狀態，類似數學中的未知數 x, y, z，都是代表某個值(狀態)
    2. 找出最後一步
       • 最後一步是答案，答案是什麼？
         • 有 k 個硬幣，a1, a2, a3...，和是 sum，所以一定有 1 枚硬幣是 ak
         • k 一定要是最小值(最少枚求出 sum - ak)
    3. 列成子問題算式
       • 設定算式：f(sum) = 最少用多少硬幣拼出 sum
       • 開始思考：假如 coins 給 1, 2, 5，ak 如果是其中一個，那可以歸納為：
         • f(sum) = f(sum - 1) + 1
         • f(sum) = f(sum - 2) + 1
         • f(sum) = f(sum - 5) + 1
         • f(sum) = min{f(sum - 1) + 1, f(sum - 2) + 1, f(sum - 5) + 1}
       • 遞迴的感覺？是可以的解，但肯定慢（重複計算多次）
    4. 轉移方程式
       • 遞迴是用 function 每次重新算，轉移方程用 list or array 來記住狀態
       • 列成 f[sum] = min(f[sum - 1] + 1, f[sum - 2] + 1, f[sum - 5] + 1)
       • 先訂出初始狀態跟 edge case:
         • f[-1] = INT32_MAX // 遇負數都要處以 INT32_MAX(表示為不可能組出的狀態)
         • f[0] = 0 // 遇 0 則返回 0 (表示無需任何硬幣的狀態)
         • 在要重新賦新狀態給 f[sum] 時，先判斷 edge case 再做
    5. 選定計算順序：通常是從小到大（因為要記狀態），f[0] = ?, f[1] = ?, f[2] = ? ... f[sum] = ?
       • 時間複雜度：一共 sum 次，每次 list.length 次，一共是 sum * list.length === n * m