动态规划--线性DP-1

线性DP：在线性空间上进行答案的递推。

1、数字三角形问题

https://www.acwing.com/problem/content/900/

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int N=510;
 5 int w[N][N],f[N][N];
 6 int main(void){
 7     memset(f,0xa0,sizeof f);//初始化为无穷小
 8     int n;
 9     cin>>n;
10     for(int i=1;i<=n;i++){
11         for(int j=1;j<=i;j++){
12             cin>>w[i][j];
13         }
14     }
15     f[1][1]=w[1][1];//第一层得初始化
16     for(int i=2;i<=n;i++){
17         for(int j=1;j<=i;j++){
18             f[i][j]=max(f[i-1][j-1]+w[i][j],f[i-1][j]+w[i][j]);
19         }
20     }
21     int res=-99999;
22     for(int i=1;i<=n;i++){
23         res=max(res,f[n][i]);
24     }
25     cout<<res;
26     return 0;
27 }

2、最长上升子序列问题

https://www.acwing.com/problem/content/897/

 1 #include<iostream>
 2 using namespace std;
 3 const int N=1010;
 4 int w[N],f[N];
 5 int main(void){
 6     int n;
 7     cin>>n;
 8     for(int i=1;i<=n;i++){
 9         cin>>w[i];
10     }
11     
12     f[1]=1;
13     for(int i=2;i<=n;i++){
14         f[i]=1;
15         for(int j=1;j<i;j++){
16             if(w[j]<w[i]){
17                 f[i]=max(f[j]+1,f[i]);
18             }
19         }
20     }
21     
22     int res=0;
23     for(int i=1;i<=n;i++){
24         res=max(res,f[i]);
25     }
26     cout<<res;
27     return 0;
28 }

3、最长上升子序列问题优化

https://www.acwing.com/problem/content/898/

那么我们就可以通过二分找到对于每一个数，他的最长的上升子序列长度是多少。

因为我们只需要二分找到不大于a[ i ] 的最大的f [ j ] ，j+1就是以a[ i ] 结尾的最长上升子序列的长度。

#include<iostream>
using namespace std;
const int N=100010;
int a[N],f[N];
int main(void){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int len=0;
    f[0]=-2e9;//设置初始状态，长度为0的结尾为-INF
    for(int i=0;i<n;i++){
        int l=0,r=len;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(a[i]<=f[mid]){
                r=mid-1;
            }else{
                l=mid;
            }
        }
        len=max(len,r+1);
        f[r+1]=a[i];
    }
    cout<<len;
    return 0;
}