#43734: 動態規劃五步法
chiuliyou@gmail.com
(邱立宇)
學校
:
新北市立永平高級中學
編號 : 136609
來源 : [61.228.158.165]
最後登入時間 ：
2024-10-26 13:36:59
1. 構造問題: 找出最長遞增子序列
2. 定義狀態: f(i) = 到 index i 為止的最長遞增子序列
3. 求解小規模的簡單問題: f(0) = 1
4. 狀態轉移方程式:
f(i) = max( f(j) + 1 | nums[i] > nums[j])
(如果 nums[i] > nums[j], 那麼 f(j) + 1 就是預備答案之一, 最後要找最大的)
5. 判斷複雜度: O(n^2)
可以透過「耐心排序」將複雜度降低到 O(nlogn), 同時節省空間