线性DP

最长上升子序列

动态规划

int a[5010],n,dp[5010];
int ans;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    dp[1]=1;
    for(int i=2;i<=n;i++){
        int MAX=0;
        for(int j=1;j<=i-1;j++){
            if(a[j]<a[i]&&MAX<dp[j]){
                MAX=dp[j];
            }
        }
        dp[i]=MAX+1;
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;

}

二分优化

int a[5010],b[5010],len,n;
int ans;
//二分查找第一个大于等于X的数
int find(int l,int r,int x){
    int ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(b[mid]>=x){
            ans=mid;
            r=mid-1;
        } else{
            l=mid+1;
        }
    }
    return ans;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    len=1;b[1]=a[1];
    for(int i=2;i<=n;i++){
        //大则添加
        if(a[i]>b[len]){
            b[++len]=a[i];
        }
        //小则替换
        else{
            int j=find(1,len,a[i]);
            b[j]=a[i];
        }

    }

    cout<<len<<endl;

}

背包

01背包

for(int i=1;i<=n;i++){
    for(int j=0;j<=V;j++){
        dp[i][j]=dp[i-1][j];
        if(j-v[i]>=0){
            dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
        }
    }
}

//空间压缩优化
for(int i=1;i<=n;i++){
    for(int j=V;j>=v[i];j--){
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

    }
}

完全背包

for(int i=1;i<=n;i++){
    for(int j=0;j<=V;j++){
        dp[i][j]=dp[i-1][j];
        if(j-v[i]>=0){
            dp[i][j]=max(dp[i][j],dp[i][j-v[i]]+w[i]);
        }
    }
}

//空间压缩优化
for(int i=1;i<=n;i++){
    for(int j=v[i];j<=V;j++){
        dp[j]=max(dp[j],dp[j-v[i]]+w[i]);

    }
}