编程笔记

线性DP

13分钟阅读

2.线性DP

状态转移方程呈现出一种线性的递推形式的DP，我们将其称为线性DP。

（一）数字三角形

AcWing 898. 数字三角形

实现思路：

  • 对这个三角形中的数字进行编号，状态表示依然可以用二维表示，即f(i,j)，i表示横坐标（横线），j表示纵坐标（斜线）
img
  • 用f(i,j)表示到点(i,j)的路径最大数字之和。对集合进行划分，到达某点(i,j)只可能经过左上方的点(i-1,j-1)或右上方的点(i-1,j)。用a[i][j]表示当前点的数值
  • 故可得状态转移方程：f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j])
#include <iostream>
#include <algorithm>
using namespace std;
const int N=510,INF=1e9;
int n;
int f[N][N],a[N][N];
 
int mian(){
    cin>>n;
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i+1;j++)//注意这里最大下标为i+1 因为在每一行的最后一个数的右上方没数但也会用到
            a[i][j]=-INF;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=i;i++)
            cin>>a[i][j];
    f[1][1]=a[1][1];//初始化到点（1,1）的最大值之和
    
    for(int i=1;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]);
    cout<<res;
    
    return 0;
}

这道题还可以从下往上递推，考虑f[i][j]来自左下方和来自右下方两种情况，这样就不需要处理边界问题，而且最后的结果一定集中在f[1][1]中。

#include <iostream>
#include <algorithm>
using namespace std;
const int N=510,INF=1e9;
int n;
int f[N][N],a[N][N];
 
int mian(){
    int n;
    cin >> n;
    for (int i= 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
            cin >> a[i][j];
            
    for (int i = 1; i <= n; i++) f[n][i] = a[n][i];
    
    for (int i = n - 1; i >= 1; i--)
        for (int j = 1; j <= i; j++)
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + a[i][j];
    
    cout << f[1][1] << endl;
    return 0;
}

（二）最长上升子序列(LIS)

AcWing 895. 最长上升子序列

实现思路：

img
  • 一维数组f[i]表示以第i个数为结尾的最长递增子序列的长度。
  • 状态划分：选定i为结尾的递增子序列，则再从[0,i-1]中筛选出倒数第二个位置的数，使递增子序列的长度最大。注意这个倒数第二个位置的数必须满足a[j]<a[i]，这样才能保证递增序列。
  • 状态转移方程为f[i]=max(f[i],f[j]+1);
  • 时间复杂度为O(n^2)
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int f[N],a[N];
int n;
int mian(){
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i],f[i]=1;//f[i]初始为1即仅包括自身
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);//得到最大值
    cout<<res<<endl;
    return 0;
}

二分优化

当数据范围扩大时，O(n^2)的时间复杂度已经不能满足要求时用二分的方法可以优化到O(nlogn)

实现思路：

  • 首先在上述解法的基础上，假如存在一个序列3 1 2 5，以3结尾的上升子序列长度为1，以1为结尾的上升子序列长度也为1，这是两个长度一样的上升子序列（伏笔：结尾元素1<3）。在继续向后遍历查找时，看3这个序列，当出现一个比3大的数时，以3结尾的上升子序列就会更新，比如遍历到5了，那么上升序列变为3 5；同时注意到这个5一定会加入到以1结尾的上升序列中（因为1<3，那么1<5的），那么含有1的上升序列长度一定是>=2的，因为中间可能存在<3但>1的数（比如这里就有2，序列长度就更新为3）。可以看出存在3的这个序列就不需要枚举了，因为存在1的序列往后遍历的长度是一定大于你这个存在3的序列的（前提是以1结尾和以3结尾的上升序列长度相等），那我找最长的时候怎么都轮不到包含3的序列头上，那我一开始在1和3结尾的序列之后直接舍弃枚举包含3的序列了（去掉冗余）。
  • 在以上的分析得到：当存在两个上升序列长度相同时，结尾数更大的序列可以舍去不再枚举，所以每次就干脆选出相同长度结尾元素最小的序列继续操作
  • 那么状态表示更改为：f[i]表示长度为i+1(因为下标从0开始)的最长上升子序列，末尾最小的数字。(所有长度为i+1的最长上升子序列所有结尾中，结尾最小的数) 即长度为i的子序列末尾最小元素是什么。
  • 状态计算：对于每一个数w[i], 如果大于f[cnt-1](下标从0开始，cnt长度的最长上升子序列，末尾最小的数字)，那就将这个数w[i]添加到当前序列末尾，使得最长上升序列长度+1(cnt++)，当前末尾最小元素变为w[i]。 **若w[i]小于等于f[cnt-1],**说明不会更新当前的长度，但之前末尾的最小元素要发生变化，找到第一个 大于或等于(不能直接写大于，要保证单增) w[i]的数的位置mid，将这个数w[i]放在mid的位置（其实就是找到w[i]适合存在的位置，不改变序列长度）。

其他参考说明：

AcWing 896. 最长上升子序列 II - AcWing

AcWing 896. 最长上升子序列 II - AcWing

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int w[N],f[N];
int n,cnt;//cnt记录最大上升序列长度
 
int mian(){
    cin>>n;
    for(int i=;i<n;i++) cin>>w[i];
    
    f[cnt++]=w[0];//初始就放一个w[0]
    
    for(int i=1;i<=n;i++){
        if(w[i]>f[cnt-1]) f[cnt++]=w[i];//w[i]大于当前上升序列末尾的数 则末尾加入
        else{//否则 二分查找当前上升序列中合适的位置插入
            int l=0,r=cnt-1;
            while(l<r){
                int mid=(l+r)>>2;
                if(f[mid]>=w[i]) r=mid;
                else l=mid+1;
            }
            //找到合适位置了
            f[r]=w[i]
        }
    }
    cout<<cnt<<endl;
    return 0;
}

（三）最长公共子序列(LCS)

AcWing 897.最长公共子序列

实现思路：

  • f(i,j)表示第一个序列的前i个字母和第二序列前j个字母最长的公共子序列长度
  • 状态可划分为4中情况：a[i]表示第一个序列中第i个字符，b[j]表示第二个子序列中第j个字符
    • 00：表示最长公共子序列中一定不包含字符a[i]和b[j]，用f[i-1][j-1]表示
    • 01：表示最长公共子序列中一定不包含字符a[i]，一定包含b[j]。不能用f[i-1][j]表示（不是等价的），因为f[i-1][j]表示的是该公共子序列一定不包含a[i]，但b[j]不一定，可能包含也可能不包含。故f[i-1][j]是包含01这种情况的。但是由于求的是最大子序列的长度（而不是具体元素），所以求解的时候可以用f[i-2][j]来求解
    • 10：表示最长公共子序列中一定包含字符a[i]，一定不包含b[j]。用f[i][j-1]求解，但含义不等价，同上。
    • 11：表示最长公共子序列中一定包含字符a[i]和b[j]，用f[i-1][j-1]+1表示，但注意需要满足a[i] = b[j]才行，因为公共子序列，既然包含a[i]、b[i]，那么两者必然相等才行
  • 注意：00的情况实质上已经被包含在01、10两种情况之中，所以可以省略，故只需求下面三种状态

更详细理解：

AcWing 897. 最长公共子序列（思路超清晰） - AcWing

AcWing 897. 最长公共子序列 - AcWing

#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int n,m;
char a[N],b[N];
int f[N][N];
 
int mian(){
    cin>>n>>m;
    cin>>a+1>>b+1;//下标从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]);//前两种情况01 10
            if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);//最后一种情况11
        }
    cout<<f[n][m];
    return 0;
}

（四）编辑距离

AcWing 902.最短编辑距离

实现思路：

  • f(i,j)表示，集合为所有将第一个字符串前i个字符变为第二个字符串前j个字符的方式的最少操作数量
  • 集合划分：以第一个字符串i处可能进行的三种不同操作后转化为第二个字符串。
    • 删去第i个字符，即前i-1个字符已经与第二个字符串的前j个字符相同，因此只需要在上一个状态加上删去操作即可，即f(i,j)=f(i-1,j)+1；
    • 增加第i个字符才能与第二个字符串的前j个字符相等，即前i-1个字符已经与第二个字符串的前j-1个字符相同，因此只需要在上一个状态加上增加第i个字符操作即可，即f(i,j)=f(i-1,j-1)+1；
    • 修改第i个字符，即前i-1个字符已经与第二个字符串的前j-1个字符相同，再比较第i个字符是否与第j个字符相同，若相同就不用操作，若不同则需要增加一次修改操作,即f(i,j)=f(i-1,j-1)+0 or 1。
  • 最终f(i,j)取三者最小值
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
char a[N],b[N];
int f[N][N];
int n,m;
 
int main(){
    //均从下标1开始
	scanf("%d%s",&n,a+1);
    scanf("%d%s",&m,b+1);
    
    for(int i=0;i<=n;i++) f[i][0]=i;//第二个字符串为空 则一直删除
    for(int i=0;i<=m;i++) f[0][i]=i;//第一个字符串为空 则一直增加
    
    for(int i=;i<=n;i++)
        for(int j=1;j<=m;j++){
            f[i][j]=min(f[i-1][j]+1,f[i][j-1]+1);//增 删
            
            if(a[i]==b[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);//最后一个字符相等 不需要改
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);//最后一个不等 需要改
        }
    cout<<f[n][m];
    return 0;
}

AcWing 899.编辑距离

**实现思路：**与上题思路一致，不过在读入时有所区别，该题需要读入n个字符串，m次问询，因此读入n个第一个字符串，然后在每次问询中读入第二个字符串，计算n个第一个字符串要变化到第二个字符串的次数，统计在规定次数内的第一个字符串有几个。

#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 15, M = 1010;
int n, m;
int f[N][N];
char str[M][N];//读入多个字符串
 
int edit_distance(char a[],char b[]){
    int al=strlen(a+1),bl=strlen(b+1);
    for(int i=0;i<=al;i++) f[i][0]=i;
    for(int i=0;i<=bl;i++) f[0][i]=i;
    
    for(int i=1;i<=al;i++)
        for(int j=1;j<=bl;j++){
            f[i][j]=min(f[i][j-1]+1,f[i-1][j]+1);
            if(a[i]==b[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);
        }
    return f[al][bl];
}
 
int main()
{
    scanf("%d%d", &n,&m);
    for (int i=0;i<n;i++) scanf("%s",str[i]+1);
    while (m--)
    {
        char s[N];
        int limit;
        scanf("%s%d",s+1,&limit);
        int res=0;
        for (int i=0;i<n;i++)
            if (edit_distance(str[i],s) <= limit)
                res ++ ;
        printf("%d\n", res);
    }
    return 0;
}