[数据结构与算法]动态规划&算法笔记

基础概念

• 状态和状态转移方程
• 重叠子问题
• 最优子结构
• 分治：子问题均不重叠
• 贪心：仅选择了一个子问题

例子

最大连续子序列和

时间复杂度O(n)

• dp[i]表示以A[i]作为结尾的连续序列的最大和
• dp[i]=max{A[i],dp[i-1]+A[i]}

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int A[maxn], dp[maxn];
int main(){
    int n;
    scanf("%d",&n);
    for(int i = 0; i < n; i++){
        scanf("%d",&A[i]);
    }
//边界
    dp[0] = A[0];
    for(int i=1; i < n; i++){
        dp[i] = max(A[i], dp[i-1] + A[i]);
    }
    int k = 0;
    for(int i=1; i < n; i++){
        if(dp[i] > dp[k]){
            k = i;
        }
    }
    printf("%d\n", dp[k]);
    return 0;
}

最长不下降子序列LIS

• dp[i]=max{1,dp[j]+1} (j=1,2,i-1; A[j]<A[i])
• LIS不一定连续

int ans = -1;//记录最大的dp[i]
for(int i = 1; i <= n; i++ ){
    dp[i] = 1;
    for(int j=1; j < i; j++){
        if(A[i] >= A[j] && (dp[j]+1 > dp[i]))//dp[j]+1 > 1不对
        {
            dp[i] = dp[j] + 1;
        }
    }
    ans = max(ans,dp[i]);
}
//A[1]-A[n]

最长公共子序列

$dp[i][j]=\{\begin{array}{l}dp[i?1][j?1]+1,A[i]==B[j]\\ max(dp[i?1][j],dp[i][j?1]),A[i]!=B[j]\end{array}$
边界：$dp[i][0]=dp[0][j]=0$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100;
char A[A],B[N];
int dp[N][N];
int main(){
    int n;
    gets(A+1);//下标从1开始读入
    gets(B+1);
    int lenA=strlen(A+1);
    int lenB=strlen(B+1);
    for(int i=0;i<=lenA;i++){
        dp[i][0]=0;
    }
    for(int i=0;i<=lenB;i++){
        dp[0][i]=0;
    }
    for(int i=1;i<=lenA;i++){
        for(int j=0;j<lenB;j++){
            if(A[i]==B[j])
                dp[i][j]=dp[i-1][j-1]+1;
            else
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    printf("%d",dp[lenA][lenB]);
    return 0;
}

最长回文串

暴力解法：枚举端点+判断回文 O($n^3$)
dp[i][j] = 1表示s[i]到s[j]所表示的子串为回文子串
$dp[i][j]=\{\begin{array}{l}dp[i+1][j?1],s[i]==s[j]\\ 0,s[i]!=s[j]\end{array}$
边界：$dp[i][i]=1;dp[i][i+1]=(s[i]==s[i+1])?1:0$
怎样保证dp[i+1][j-1]是已经计算过的值？以字串的长度和字串的初始位置进行枚举 因为每次转移时都对字串的长度减了1

#include <cstdio>
#include <cstring>
const int maxn = 1010;
char s[maxn];
int dp[maxn][maxn];
int main(){
    gets(s);
    int len = strlen(s),ans=-1;
    memset(dp,0,sizeof(dp));//dp数组初始化为0、
    //边界
    for(int i=0;i<len;i++){
        dp[i][i]=1;
        if(i<len-1){
            if(s[i]==s[i+1]){
                dp[i][i+1]=1;ans=2;
            }
        }
    }
    for(int L=3;L<len;L++){
        for(int i=0;i+L-1<len;i++){
            int j=i+L-1;
            if(s[i]==s[j]&&dp[i+1][j-1]==1){//是回文串
            /*dp[i+1][j-1]更短*/
                dp[i][j]=1;ans=L;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}