2023.3.17

[TOC]

DP解题思路

分解子问题
- 根据题目特点，合理划分解决问题的阶段，每个阶段都解决一个和原问题相同的子问题
- 子问题能解决，原问题就可以解决
- 子问题的结果被保存，确保每个子问题只计算一次
确定状态
- 对于每个子问题，相关变量的一组取值，叫做一个状态
- 一个状态的值，就是这个状态下子问题的解
- 状态の集合，叫做本问题的状态空间
- 比如一个状态可以用k个整数表示，状态空间一般是k维数组
- 状态该的值不一定是一个整数，可以是一个数据结构
状态转移
- 首先确定Init初始状态（比如：fib(1)=fib(0)=1)
- 确定状态之间如何迁移(比如：fib(n)=fib(n-1)+fib(n-2)，为状态转移方程)

DP能解决问题的特点

最优子结构：问题的最优解所包含的子问题的解是最优的。
无后效性：当前的若干个状态值一旦确定，则后续过程的演变就只与当前状态的值有关。和之前演变路径无关。

这个就和图论不太一样，比如BF算法就会和之前的状态的值相关捏。

线性DP

所有的状态是在一个线性状态下进行递推。

最长上升子序列问题(LIS)

dp[i]:以数组第i个数截为的最长上升子序列的最大长度

dp[i]=max{dp[j]}+1(j<i,a[j]<a[i],边界条件：dp(1)=1)

最终答案是max{dp(i)}：求完dp数组后再取max

==时间复杂度：O($n^2$)==

P1020

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

dilworthd定理:

用最长不上升子序列覆盖整个序列，所需要的最少个数=最长上升序列长度

用最长上升子序列覆盖整改序列，所需要的最少个数=最长不上升序列长度

所以P1020相当于求一个最长不上升子序列，再求一个最长上升子序列。

int a[100005],dp[100005];
for(int i=1;i<=N;i++){
    dp[i]=1;
    for(int j=1;j<i;j++){
        if(a[j]<a[i])dp[i]=max(dp[i],dp[j]+1);
    }
    ans=max(ans,dp[i]);
}

由于这个的算法复杂度为O($n^2$)，需要将算法优化到O($nlogn$)才能过。

二分优化时间复杂度

dp[i]：表示长度为i的上升子序列的最小的结尾。

index	1	2	3	4	5	6	7
a	1	7	3	5	9	4	8
dp_1	1	7
dp_2	1	3
dp_3	1	3	5
dp_4	1	3	5	9
dp_5	1	3	4
dp_6	1	3	4	8

int max_length=0;
dp[0]=200000;
for(int i=1;i<n;i++){
    if(dp[max_length]>=a[i]){//计算的是最长不上升子序列，所以要小才好
        dp[++max_length]=a[i];
    }else{//二分
        int l=1,r=max_length;
        while(l<r){
            int mid=(l+r)>>1;
            if(dp[mid]<a[i]){
                ans=mid;
                r=mid-1;
            }else{
                l=mid+1;
            }
        }
        dp[ans]=a[i];
    }
}

POJ1458

最长公共子序列：子序列中的每个字符都能在两个原串中找到，而且每个字符的先后顺序与原串中的先后顺序一致。

设：$len_1=strlen(s_1),len_2=strlen(s_2)$，则题目要求求$f(len1,len2)$.

初始条件：$f(i,0)=0\ i=1,2,…,len1$，$f(0,j)=0\ j=1,2,…,len2$
$$
f(i,j)=\begin{cases}
f(i-1,j-1)+1,&s_1[i]=s_2[i]\
max(f(i,j-1),f(i-1,j)),&s_1[i]\ne s_2[i]\
\end{cases}
$$

P2758-编辑距离

设 $A$ 和 $B$ 是两个字符串。我们要用最少的字符操作次数，将字符串 $A$ 转换为字符串 $B$。这里所说的字符操作共有三种：

删除一个字符；
插入一个字符；
将一个字符改为另一个字符。

$A, B$ 均只包含小写字母。

dp[i][j]：表示第一个串用到第i个字符，第二个串用到第j个字符的最小边集距离。

IF a[i]==b[j]：匹配，dp[i][j]=dp[i-1][j-1]

ELSE：有三种处理方式：

去掉a[i]
去掉b[j]
改写a[i]->b[j]

$$
dp[i][j]=\begin{cases}
dp[i-1][j-1],&a[i]=b[j]\
min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j])+1,&a[i]\ne b[j]\
\end{cases}
$$

int dp[2005][2005];
int main(){
    char a[2005],b[2005];
   
    cin>>(a+1)>>(b+1);//表示从a[1]开始输入数据
	a[0]=' ',b[0]=' ';
    int len_a=strlen(a),len_b=strlen(b);
    for(int i=0;i<len_a;i++){dp[i][0]=i;}//这个是当一串子串为空，另一串不为空时需要的编辑距离
    for(int j=0;j<len_b;j++){dp[0][j]=j;}
    for(int i=1;i<len_a;i++){
        for(int j=1;j<len_b;j++){
            if(a[i]==b[i]){
                dp[i][j]=dp[i-1][j-1];
            }else{
                dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])+1;
            }
        }
    }
    cout<<dp[len_a-1][len_b-1];
}