动态规划——线性dp

数字三角形

// 从上到下
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[N][N];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= i; j ++ )
            scanf("%d", &a[i][j]);

    for (int i = 0; i <= n; i ++ )
        for (int j = 0; j <= i + 1; j ++ )
            f[i][j] = -INF;

    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 res = -INF;
    for (int i = 1; i <= n; i ++ ) res = max(res, f[n][i]);

    printf("%d\n", res);
    return 0;
}

// 从下到上
#include<iostream>
using namespace std;
const int N = 510;
int n, a[N][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 = n - 1; i > 0; i--){
        for(int j = 1; j <= i; j++){
            a[i][j] += max(a[i + 1][j], a[i + 1][j + 1]);
        }
    }
    cout<<a[1][1];
    return 0;
}

最长上升子序列

#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int a[N], f[N];
int n, res;

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    for(int i = 1; i <= n; i++){ 
        f[i] = 1;
        for(int j = 1; j < i; j++){
            if(a[i] > a[j]) f[i] = max(f[i], f[j] + 1);
        }
        if(f[i] > res) res = f[i];
    }
    cout<<res;
    return 0;
}

// 求这个序列
#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int a[N], f[N];
int g[N], b[N];
int n;

int main(){
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>a[i];
    int k = 1;
    for(int i = 1; i <= n; i++){ 
        f[i] = 1;
        for(int j = 1; j < i; j++){
            if(a[i] > a[j]){
                if(f[i] < f[j] + 1){
                    f[i] = f[j] + 1;
                    g[i] = j;
                }
            }
        }
        if(f[i] > f[k]) k = i;
    }
    cout<<f[k]<<endl;
    int cnt1 = f[k], cnt2 = f[k];
    for(int i = 0, len = f[k]; i < len; i++){
        b[cnt1--] = a[k];
        k = g[k];
    }
    //for(int i = 1; i <= cnt2; i++) cout<<b[i]<<" ";
    return 0;
}

最长上升子序列 II

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n;

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int len = 0;
    for(int i = 1; i <= n; i++){
        int l = 0, r = len + 1;
        while(l + 1 < r){
            int mid = (l + r) / 2;
            if(b[mid] < a[i]) l = mid;
            else r = mid;
        }
        len = max(len, r);
        // b[l] 是小于 a[i] 的最后一个数
        b[r] = a[i];
    }
    printf("%d", len);
    return 0;
}

最长公共子序列

#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int f[N][N];
int n, m;
string a, b;

int main(){
    cin>>n>>m>>a>>b;
    int res = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i - 1] == b[j - 1]) f[i][j] = f[i - 1][j - 1] + 1;
            else{
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
            }
            res = max(res, f[i][j]);
        }
    }
    cout<<res;
    return 0;
}

最短编辑距离

#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int f[N][N];
int n, m;
string a, b;

int main(){
    cin>>n>>a>>m>>b;
    for(int i = 0; i <= n; i++) f[i][0] = i;
    for(int j = 0; j <= m; j++) f[0][j] = j;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(a[i - 1] == b[j - 1]) f[i][j] = f[i - 1][j - 1];
            else{
                f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
            }
        }
    }
    cout<<f[n][m];
    return 0;
}

编辑距离

#include<iostream>
using namespace std;
const int N = 1e3 + 10;
int f[15][15];
int n, m;
string s[N];

int main(){
    cin>>n>>m;
    for(int i = 0; i < n; i++) cin>>s[i];
    string a;
    int x;
    while(m--){
        cin>>a>>x;
        int cnt = 0;
        for(int k = 0; k < n; k++){
            int x1 = a.size(), x2 = s[k].size();
            for(int i = 0; i <= x1; i++) f[i][0] = i;
            for(int j = 0; j <= x2; j++) f[0][j] = j;
            for(int i = 1; i <= x1; i++){
                for(int j = 1; j <= x2; j++){
                    if(a[i - 1] == s[k][j - 1]) f[i][j] = f[i - 1][j - 1];
                    else{
                        f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
                    }
                }
            }
            if(f[x1][x2] <= x) cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}