DP

Dynamic Programming 動態規劃

經典例子：階乘

以空間換時間。把做過的答案記下來，不要再重做了。

$arr= array(); //做過的

function factorial() {
    $arr[0] = 0;
    $arr[1] = 1;
    for ($i = 2; $i<10; $i++) {
        $arr[$i] = $arr[$i-1] * $i; //做過的存起來 * 這一輪要做的事情
    }
}

只用一個變數存

$ans = 1;

function factorial() {
    for ($i = 2; $i<10; $i++) {
        $ans = $ans * $i; //做過的存起來 * 這一輪要做的事情
    }
}

應用

1. recurrence
2. 計算
3. state, DAG
4. bitset
5. stack, deque
6. convex hull
7. unimofal function 單峰函數
8. totally monotone matrix
9. interval

http://web.ntnu.edu.tw/~algo/DynamicProgramming.html