其他DP

区间dp

原理

区间DP是在区间上进行动态规划，本质是用更小区间的最优解来求更大区间的最优解。

模板

for (int len = 2; len <= n; len ++ )
    for (int i = 1; i + len - 1 <= n; i ++ )
    {
        int j = i + len - 1;
        for (int k = i; k < j; k ++ )
            f[i][j] = max(f[i][j], f[i][k] + f[k][j] + ****);
    }

例题

AW.284 石子合并（简单）

状压dp

状压DP分为两类，一类是棋盘式（基于连通性）的模型，另一类是基于集合。

棋盘式原理

蒙德里安的梦想这道题，是求把NM的棋盘分割成若干个12的的长方形，有多少种方案。通过将每一列看成一个状态，其中放了小块的格子为1，没放的为0，这样可以通过枚举所有的状态到状态的转移来进行计数。

基于集合原理

最短哈密尔顿路径，给定一张 n 个点的带权无向图，点从 0~n-1 标号，求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。对所有点构成的集合考虑，已经走过的点为1，还没有到达过的点为0，可以确定一个n位状态state，但如果需要从一个点转移到下一个点，则还需要记录当前停在了哪一个点上。因此用f[state][j]表示到达j号点时，已经走过的状态为state的路径集合中的最小值。

因此可以得到状态转移方程：

$f[state][j] = min(f[state][j], f[state - (1 << k)][k] + w[k][j]), state >> k \ \& \ 1 = 1$

当然如果从终点考虑，这样的转移方程也是合法的：

$f[i \ \| \ (1 << k)][k] = min(f[i \ \| \ (1 << k)][k], f[i][j] + d[j][k]), state >> k\ \& \ 1 = 0$

基于集合模板

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const long N = 21, M = 1 << N;
int n;

int f[M][N];
int d[N][N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            scanf("%d", &d[i][j]);


    memset(f, 0x3f, sizeof f);
    f[1][0] = 0;

    for (int i = 0; i < 1 << n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (i >> j & 1)
                for (int k = 0; k < n; k ++ )
                    //if (i >> k & 1)
                        //f[i][j] = min(f[i][j], f[i - (1 << j)][k] + d[k][j]);
                    if (!(i >> k & 1))
                        f[i | (1 << k)][k] = min(f[i | (1 << k)][k], f[i][j] + d[j][k]);

    cout << f[(1 << n) - 1][n - 1] << endl;

    return 0;
}

LIS问题

原理

LIS问题有两种解法，基于动态规划定义f[i]为以i结尾的最长上升子序列的最大长度。如果基于贪心，将i之前所有上升子序列长度存储下来，则可以发现其必然是单调上升的，因此可以通过二分来优化时间复杂度为O(nlogn）。

关于贪心解法的证明：

首先我们发现，在求解LIS问题时，如果a b c序列，c可以接到a后边即c > a，那么如果b < a则c一定也可以接到b后边。因此在这种思想的指导下，我们可以存储i位置之前所有长度的上升子序列的最后一位的最小值。
其次，对于上述存储方式，我们发现应该是单调递增的。因为如果长度为x的末尾的值，大于长度x + 1末尾的值，则在长度x + 1的情况下，一定存在一个长度为x的序列，其末尾值又严格小于现在x的末尾的值，由此发现不是最小值，矛盾，因此一定是严格上升的。

模板

//基于DP的O(n^2)解法
for (int i = 1; i <= n; i ++ )
{
    f[i] = 1;
    for (int j = 1; j < i; j ++ )
        if (a[i] > a[j])
            f[i] = max(f[i], f[j] + 1);
}

//基于贪心的O(nlogn)的解法
int q[N];
int a[N];

int len = 0;
q[0] = -2e9; //哨兵，表示长度为0的最长上升子序列的末尾值
for (int i = 0; i < n; i ++ )
{
    int l = 0, r = len;
    while (l < r)
    {
        int mid = l + r + 1 >> 1;
        if (q[mid] < a[i]) l = mid; //如果q[mid] < a[i]表示当前的mid的值比a[i]要小，因此mid可以再大点
        else r = mid - 1;
    }
    len = max(len, r + 1);
    q[r + 1] = a[i];
}

cout << len << endl;

例题

LC.718 最长重复子数组（中等）

LIS + LCS的混合定义，和下边的LCS问题一起参考

LCS问题

原理

一般两个序列的匹配问题可以考虑是不是LCS问题。这里f[i][j]的定义是匹配到A序列的第i个字符和B序列的第j个字符位置时，最长公共子序列的长度。如此定义不需要考虑是否当前最后一位被选择，因为如果最后一位字符两个序列不相同，则最长就是再之前的匹配结果f[i - 1][j]和f[i][j - 1]中的最大值。这里没有连续性的要求。

模板

//下方例题1
#include <iostream>
#include <cstring>

using namespace std;

const int N = 1010;

char a[N], b[N];
int f[N][N];

int n, m;

int main()
{
    cin >> n >> m;
    cin >> a + 1 >> b + 1;

    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= m; j ++ )
            if (a[i] == b[j]) f[i][j] = f[i - 1][j - 1] + 1;
            else f[i][j] = max(f[i - 1][j], f[i][j - 1]);

    cout << f[n][m] << endl;

    return 0;
}

//下方例题2
int dp[510][510];
class Solution {
public:
    int maxDotProduct(vector<int>& A, vector<int>& B) {
        //dp[i][j]表示考虑A[i]和B[j]时的最大值，A[i]和B[j]要么都选，要么都不选

        int n = A.size(), m = B.size();
        memset(dp, -0x3f, sizeof dp);

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
            {
                dp[i][j] = A[i - 1] * B[j - 1];
                dp[i][j] = max({dp[i][j], dp[i - 1][j - 1] + A[i - 1] * B[j - 1], dp[i - 1][j], dp[i][j - 1]});
            }

        return dp[n][m];
    }
};

例题

AW.899 最长公共子序列（简单）

LC.1458 两个子序列的最大点积（困难）

动态规划（二）其他DP