DP

Thanks my buddy tought me in a easily-understand way.

1. 遞迴
2. 筆記本
3. 下到上

f(1) = 1
f(2) = 1
f(3) = 2 = f(2) + f(1)
f(4) = f(3) + f(2)
f(5) = f(4) + f(3) = f(3) + f(2) + f(3) = f(2) + f(1) + f(2) + f(2) + f(1)

...
f(n) = f(n-1) + f(n-2)



// return f(n)
// DP
// n <= 1000
int arr[1001];
Zero(arr);
arr[1] = 1; // f(1) = 1
arr[2] = 1; // f(2) = 1
int f(int n) {
        if(arr[n] != 0) return arr[n];
        else return arr[n]=(f(n-1) + f(n-2));
}    
     
f(4) + f(3)
f(3) + f(2) + f(3)
f(2) + f(1) + f(2) + f(3)
2 + f(2) + f(3) // arr[3] = 2

int f(int n) {
        if(n == 1 || n == 2) return 1;

        // n >= 3
        int n_1 = 1 /* f(2) = 1 */,
            n_2 = 1 /* f(1) = 1 */,
            n;

        for(int i = 3; i <= n; ++i) {
                n = n_1 + n_2;
                n_2 = n_1;
                n_1 = n;
        }

        return n;
}