动态规划总结

线性区间动态规划

区间最值(RMQ)静态版问题

给出序列 \(a_1 \to a_n\)，有 \(l\) 与 \(r\) （$ l - r \ge 0 $ ），使得 \(S = \sum_{i=l}^{r} a_i\) 最大，求\(S\)。

状态转移方程：\(f[i]=\max\{ 0,f[i-1] \} + a_i\)。其中 \(i\) 是以 \(i\) 结尾的最大值。

样例如下：

[INPUT]
5
1 2 3 4 -114514
[OUTPUT]
10

结果就是 \(\max _{i=1} ^{i=n} f[i]\)。

时间复杂度为 \(O(n)\)。

参考代码如下：

int rmq(){
    memset(f,0xaf,sizeof(f));
    int result = INT_MIN;
    for(int i=1;i<=n;i++){
        f[i]=max(0,f[i-1])+a[i];
        result = max(result,f[i]);
    }
    return result;
}

最长公共子序列(LCS)

给出两个序列 \(a\) 与 \(b\)，求最长公共子序列长度。

设 \(i,j\)为\(a[1:i],b[1:j]\)时的最长公共子序列长度。

则有：

\[\text{if } a[i] = b[j] \]

\[\text{ }f[i][j]=f[i-1][j-1]+1 \]

\[\text{else} \]

\[\text{ }f[i][j]=max \{ f[i-1][j], f[i][j-1] \} \]

时间复杂度为 \(O(n^{2})\)。

int lcs(){
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(a[i]!=b[j]){
                f[i][j]=max(f[i-1][j],f[i][j-1]);
            }
            else{
                f[i][j]=f[i-1][j-1]+1;
            }
        }
    }
    return f[n][n];
}