# 動態規劃
1.把計算過的資料存下來,等到需要時可直接用不須重複計算
2.利用分治把大問題拆成很多小問題
### 費式數列
遞迴關係:f(n)=f(n-1)+f(n-2)

**程式碼**

 #include<iostream>
 #include<cstring>
 using namespace std;
 #define Max 1000005
 int arr[Max];
 int Fib(int n){
     if(n==0||n==1)return 1;
     if(arr[n]!=-1)return arr[n];
     arr[n]=Fib(n-1)+Fib(n-2);
     return arr[n];
}

int main(){
    int n;
    cin>>n;
    memset(arr,-1,sizeof(arr));
    for(int i=0;i<n;i++)
        cout<<Fib(i)<<' ';
}

### 背包問題

解法:每個物品選擇要放或不放

**程式碼:**

#include<iostream>
#include<cstring>
using namespace std;
#define Max 100
#define N 1000
int w[N+1],v[N+1];
int dp[N+1][Max+1];

int main(){
    int n,W;
    cin>>n;
    W=100;
    memset(dp,0,sizeof(dp));
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=W;j++){
            if(j<w[i])
                dp[i][j]=dp[i-1][j];
            else
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
        }
    cout<<dp[n][W];
}

### LIS(最長遞增子序列)
子序列長度為以第i個做結尾再加1
答案為計算所有以i結尾的LIS再取最大值
時間複雜度O(n^2)

**程式碼**

#include<iostream>
#include<cstring>
using namespace std;
int dp[105];
int arr[105];
int ans=1;

int LIS(int n){
    if(n==1)return 1;
    if(dp[n]!=-1)return dp[n]; //可直接使用以計算過數值(以i結尾的最長子序列)
    int ans=1;
    for(int i=1;i<n;i++){
        if(arr[n]>arr[i]){
            int k=LIS(i)+1; //如果為遞增長度就再加1
            if(k>ans)ans=k; //若有更長的子序列就更新
        }
    }
    dp[n]=ans;
    return ans;
}

int main(){
    int n;
    cin>>n;
    memset(dp,-1,sizeof(dp));
    for(int i=1;i<=n;i++)cin>>arr[i];
    
    //用for跑一遍以i結尾的LIS
    for(int i=1;i<=n;i++){  
        int x=LIS(i);
        if(x>ans)ans=x;
    }
    cout<<ans<<'\n';
}