2023.1.6 DP 学习日志

今天还是学DP，干了两道题

1.最长上升子序列II(AcWing.896)

数据加强版的最长上升子序列不能直接DP，还得二分（其实有点像贪心）

比较简单思路就不写了。其实我WA了五次

code：

#include <bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return (f==1)?x:-x;
}
ll n=read(),l,r,ans,mid,a[N],b[N];
int main()
{
    ios::sync_with_stdio(0);cout.tie(0);
    b[0]=-1e9+5;
    for(ll i=1;i<=n;i++) a[i]=read();
    for(ll i=1;i<=n;i++)
    {
        l=0,r=ans;
        while(l<r)
        {
            mid=l+r+1>>1;
            if(b[mid]<a[i]) l=mid;
            else r=mid-1;
        }
        ans=max(ans,r+1);
        b[r+1]=a[i];
    }
    cout << ans;
    return 0;
}

2.最短编辑距离（AcWing.902）

• 其实是一道字符串DP
• 其实这道题我的最大收获是搞清楚了cin >> s+1;或scanf("%s",s+1);的必要条件是char s[N];而不是string s，怪不得之前总CE。我居然到现在才知道

做法：

思路来喽，嗨嗨~

1. 表示状态
   设f[i][j]表示 \(a\) 的前 \(i\) 个字符转换成 \(b\) 的前 \(j\) 个字符所需的最少步骤。

2. 循环范围
   \(i\) 表示 \(a\) 的字符，\(a\) 的最大下标为 \(n\),因此 \(i\) 的循环范围是 1~\(n\) 。
   \(j\) 表示 \(b\) 的字符，\(b\) 的最大下标为 \(m\),因此 \(j\) 的循环范围是 1~\(m\) 。

3. 状态转移
   f[i][j]的取值是Min{f[i][j-1]+1,f[i][j-1]+1,f[i-1][j-1]+1}

   其中，
   f[i][j-1]+1表示通过删字符的最小步骤；
   f[i][j-1]+1表示通过增字符的最小步骤；
   f[i-1][j-1]+1表示通过改字符的最小步骤。

有了这些，就可以打出code：

#include <bits/stdc++.h>
#define ll long long
#define N 1005
using namespace std;
inline ll read()
{
    ll x=0,f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-f;c=getchar();}
    while(isdigit(c)){x=x*10+c-48;c=getchar();}
    return (f==1)?x:-x;
}//卡长
ll n,m,maxn,f[N][N];
char a[N],b[N];
void init()
{
    for(ll i=0;i<=maxn;i++)
    {
        if(i<=n) f[i][0]=i;
        if(i<=m) f[0][i]=i;
    }/*更好理解的写法：
    for(ll i=0;i<=n;i++) f[i][0]=i;//如果b的长度为0，a要转换成b只能通过删去i个字符
    for(ll i=0;i<=m;i++) f[0][1]=i;//如果a的长度为0，a要转换成b只能通过添加i个字符
*/}
int main()
{
    n=read();cin >> a+1;
    m=read();cin >> b+1;
    maxn=max(n,m);
    init();//初始化
    for(ll i=1;i<=n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            f[i][j]=min(f[i][j-1],f[i][j-1])+1;
            if(a[i]==b[j]) f[i][j]=min(f[i][j],f[i-1][j-1]);//如果a[i]等于b[j]那就不需要再操作
            else f[i][j]=min(f[i][j],f[i-1][j-1]+1);//否则，就还需操作一次
        }
    }
    cout << f[n][m];
	return 0;
}