動態規劃(dynamic programming)

終於到了我心中的大大大大魔王，這是我目前學到最難做最難想的演算法，運用到的許多遞迴的觀念還有分治演算法的概念，所以對遞迴和分治法要夠熟來解決dp才能得心應手。
但dp的難度真的太高，所以這邊只會紀錄最基礎的部分。
一般如果要進行費氏數列的運算會利用遞迴做，f(n-1)+f(n-2)

#include <iostream>
using namespace std;
int f(int n){
    if(n == 1 || n == 2) return 1;
    return f(n-1)+f(n-2);
}
int main(){
    for(int i = 1;i <= 10;i++){
        cout << f(i) << " ";
    }
    cout << endl;
    
    return 0;
}

雖然此方法可行，但是當數字過大的時候他就沒辦法運算，此時就要用到動態規劃法，這樣可以算到很大的數字。

#include <iostream>
using namespace std;
int main(){
    long long int f[100];
    f[0] = 1;
    f[1] = 1;
    for(int i = 2;i < 80;i++)
        f[i] = f[i-1]+f[i-2];
    cout << f[69] << endl;//ouput = 190392490709135
    
    return 0;
}