动态规划（线性）

daimazhishen / 2024-02-06 / 原文

898. 数字三角形

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

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,INF=1e9;
int n;int a[N][N],p[N][N];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;j++)
            cin>>a[i][j];
    //初始化，便于后面更新
    memset(p,-0x3f3f3f3f,sizeof p);
    //切记头一个初始化
    p[1][1]=a[1][1];
    
    for(int i=2;i<=n;i++)
        for(int j=1;j<=i;j++)
            p[i][j]=max(p[i-1][j-1]+a[i][j],p[i-1][j]+a[i][j]);
    //最大值在最后一排，但不一定是最后一个，需要求解
    int res=-INF;
    for(int i=1;i<=n;i++) res=max(res,p[n][i]);
    cout<<res<<endl;
    
    return 0;
}

最长子序列

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

（可以不相邻取子串）

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n;int a[N],p[N];
int main()
{
   cin>>n;
   for(int i=1;i<=n;i++)
    cin>>a[i];
    
    for(int i=1;i<=n;i++)
    {
        p[i]=1;//只有a[i]一个数
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i]) p[i]=max(p[i],p[j]+1);
        }
    }
    
    int ans=0;
    for(int i=1;i<=n;i++) ans=max(ans,p[i]);
    
    cout<<ans<<endl;
    return 0;
}

求路径

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
int n;int a[N],p[N],s[N];
int main()
{
   cin>>n;
   for(int i=1;i<=n;i++)
    cin>>a[i];
    
    for(int i=1;i<=n;i++)
    {
        p[i]=1;//只有a[i]一个数
        s[i]=0;
        for(int j=1;j<i;j++)
        {
            if(a[j]<a[i]) {
                if(p[j]+1>p[i])
                {
                    p[i]=p[j]+1;
                    s[i]=j;//记录上一个位置的下标
                }
            }
        }
    }
    
    int ans=0;int k;
    for(int i=1;i<=n;i++){
        if(p[i]>ans){
        ans=p[i];
        k=i;
        }
    } 
    
    cout<<ans<<endl;
    
    for(int i=k;i!=0;i=s[i])//倒叙遍历输出
        cout<<a[i]<<" ";
        
    return 0;
}

最长公共子序列（字符串）

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

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

分组DP

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

#include<iostream>
using namespace std;
const int N=1010;
int sum[N];int a[N];int p[N][N];
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
    for(int len=2;len<=n;len++){//区间长度
        for(int i=1;i+len-1<=n;i++){//枚举区间开头
            int j=i+len-1;//区间结尾
            p[i][j]=1e9+10;
            for(int k=i;k<j;k++)//区间内不同分段
            {
                p[i][j]=min(p[i][j],p[i][k]+p[k+1][j]+sum[j]-sum[i-1]);
            }
        }
    }
    cout<<p[1][n]<<endl;
    return 0;
}