线性dp

数字三角形

acwing例题

#include<iostream>
#include<cstring>
using namespace std;
const int N = 510 ;
int f[N][N] , a[N][N];
int n ;
int main()
{
    cin >> n ;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= i ; j++)
            cin >> a[i][j] ;

    for(int i = 0 ; i <= n ; i++)
    {
        for(int j = 0 ;  j <= i + 1 ; j++)
        {
            f[i][j] = -(1e9 + 10);
        }
    }
    
    f[1][1] = a[1][1] ;
    
    for(int i = 2; i <= n ; i++)
    {
        for(int j = 1; j <= i ; j++)
        {
            f[i][j] = max(f[i-1][j-1] + a[i][j] , f[i-1][j] + a[i][j]);
        }
    }
    int ans = -1e9 ;
    int t = n ;
    for(int i = 0 ; i <= t ; i++) ans = max(ans , f[n][i]) ;
    cout << ans;
    return 0;
}

最长上升子序列

acwing例题

#include<iostream>
using namespace std ;
const int N = 1010 ;
int a[N];
int f[N];
int n;
int main()
{
    cin >> n ;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> a[i];
        f[i] = 1;
    }
    
    for(int i = 2 ; i <= n ; i++)
    {
        for(int j = 1; j < i ; j++)
        {
            if(a[i] > a[j]) f[i] = max(f[i] , f[j] + 1);
        }
    }
    int ans ;
    for(int i = 1 ; i <= n ; i++) ans = max(ans,f[i]);
    cout << ans ;
    return 0;
}

最长上升子序列II

acwing例题

#include<iostream>
#include<cstring>
using namespace std ;
const int N = 1e5 + 10;
int a[N] , q[N];
int n;
int main()
{
    cin >> n ;
    for(int i = 0 ; i < n ; i++) cin >> a[i];
    
    int len = 0 ;
    for(int i = 0 ; i < n ; i++)
    {
        int l = 0 , r = len ;
        while(l < r)
        {
            int mid = (l + r + 1) >> 1 ;
            if(q[mid] < a[i]) l = mid ;
            else r = mid - 1;
        }
        q[r+1] = a[i];
        len= max(len,r+1);
    }
    
    cout << len ;
    return 0;
}

最长公共子序列

点击跳转至例题

#include<iostream>
#include<cstring>
using namespace std ;
const int N = 1010 ;
int n , m ;
char a[N] , b[N];
int f[N][N];
int main()
{
    cin >> n >> m >> a+ 1 >> b + 1 ;
    for(int i= 1 ; i <= n ; i++)
    {
        for(int j = 1 ; j <= m ; j++)
        {
            f[i][j] = max(f[i-1][j] , f[i][j-1]);
            if(a[i] == b[j]) f[i][j] = max(f[i-1][j-1] + 1 , f[i][j]) ;
        }
    }
    cout <<f[n][m];
    return 0 ;
}