接下来是 DP, 感觉本科时候做的题太少了，见到题不知道怎么用。

动态规划

动态规划(dynamic programming) 中的 programming 并非编程，而是列表格的意思。它也是通过合并子问题的解来得到原问题的解，不过与分治法不同，动态规划分割出的子问题是相互重叠的，即子问题之间有着公共的子问题。通过在运算过程中记录下子问题的解，免去了公共子问题的重复求解。

动态规划通常用于求解最优化问题(optimization problem),即从问题的若干可行解中找到具有最优值的。

用动态规划求解问题一般遵循以下步骤：

刻画出最优解的结构特征
递归定义出最优解的值
计算并构造出最优解

动态规划有两种实现方式：一种是自上而下递归求解，过程中同时记录子问题的解；另一种是自底向上按照一定顺序迭代求解。一般情况下都用后者，无递归开销且记录比较方便。

动态规划适用的问题一般有两个特征：重叠子问题(overlapping subproblem) 和 最优子结构(optimal substructure)

重叠子问题

重叠子问题就是说子问题之间有重叠的公共部分。

考虑之前在分治法提到的归并排序，最终划分出的子问题都是彼此独立的，最后只要简单的合并子问题的解即可。而比如递归求菲波纳契数列，在算 f(4) 的时候要算 f(3), 算 f(5) 的时候还要算 f(3), 同理它们也都需要 f(2) 的值，这些子问题的值在递归时被反复求解，这样的子问题划分就属于重叠子问题。

最优子结构

对于一个最优化问题，如果子问题的最优解能够组合成原问题的最优解，那么这个问题就具有最优子结构。

一个简单的例子：一个人在二维矩阵里面走，只能向下向右，每个点有个值，问左上角走到右下角的最小值。这里只要每一步也就是每个子问题都选最优解，最终走到右下角的最优解就能够由这些子问题的最优解构成。

经典实例

最长公共子序列 LCS

给两个字符串，求出它们的最长公共子序列的长度(或求这个序列)。例如 “13579” 和 “12345” 的最长公共子序列是 “135”.

如果串1为$ X=x_0x_1x_2…x_m $, 串2为 $ Y=y_0y_1y_2…y_n $, 用 $dp_{ij}$ 表示 $X_{0…i}$ 到 $Y_{0…j}$ 的最长公共子序列长度的话，可以得到递推式

$$ dp_{ij}= \begin{cases} 0 & i=j=0 \cr dp_{i-1,j-1} + 1, & X_{i}=Y_{j} \cr max \lbrace dp_{i,j-1}, dp_{i-1,j} \rbrace & X_{i} \neq Y_{j} \cr \end{cases} $$

实现没啥特殊的，就是两重循环。如果要找到确切的一个最长公共子序列，需要回溯回去。从填好的数组右下角开始，判断是从哪个方向到达这个状态的，如果与左和上都不同，说明是左上+1得到的，否则往左或上选一个回溯，直到退回到值为 $0$ 的地方，就可得到其中一个 LCS。

0-1 背包

有一系列物品，每个都有自己的价值和总量。要从中选一些放到包里，要求不能超重，取得最大的价值。

用 $dp[i][j]$ 表示前$i$个物品决策后重量为$j$的背包的最大值，状态转移方程为

$$f[i][j] = max{f[i - 1][j], f[i - 1][j - weight[i]] + value[i]} $$

二维数组的写法

int knapsack(int n, int W, int *v, int *w, int *dp)
{
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= W; j++) {
            if (w[i] > j) {
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
            }
        }
    }
    return dp[n - 1][W];
}

观察可以看出可用一维数组存结果，但是注意每次更新时因为需要上一轮循环中重量比现在小的那个值，所以要从后往前循环才行。

int knapsack(int n, int W, int *v, int *w, int *dp)
{
    for (int i = 0; i < n; ++i) {
        for (int j = W; j >= w[i]; --j) {
            dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
        }
    }
    return dp[W];
}

除了简单的 01背包，还有若干变种问题，可见著名的背包问题九讲

矩阵连乘

给出一系列矩阵需要求连乘，给计算加上括号，制定一个最优的计算顺序，使得计算需要的乘法次数最小

如果暴力枚举，根据组合数学学的东西，将有卡特兰数$\frac{1}{n+1}\tbinom{2n}{n}$这么多的加括号方法。

用 dp 来做呢，用 $dp[i][j]$ 表示从$i$乘到$j$所需要的最小计算次数，那么状态转移函数：

$$ dp_{ij} = \begin{cases} 0 & i=j \cr min \lbrace dp[i][k]+dp[k+1][j] + p_{i-1}p_kp_j \rbrace & i \le k < j \end{cases} $$

从两个矩阵、三个矩阵一直算到最后，每次从中间寻找一个最优的分割点

如果要回溯结果可以用另一个辅助的矩阵记住每次的最优分割点递归打印

编辑距离

给出两个字符串，要求通过下面三种方式处理，使得最后两个字符串相同，求最小的步骤数：

插入一个字符
删除一个字符
替换一个字符

用类似 LCS 的方式表示子问题，分别考虑三种情况，那么状态转移函数：

$$ dp_{ij}=\begin{cases} i & j=0 \cr j & i=0 \cr dp_{i-1,j-1}, & X_{i}=Y_{j} \cr min \lbrace dp_{i,j-1}, dp_{i-1,j}, dp_{i-1,j-1} \rbrace +1 & X_{i} \neq Y_{j} \end{cases} $$

无脑的实现就按照状态转移函数来就行，其实空间可以优化成一维数组存

int minDistance(string word1, string word2) {
    int m = word1.length();
    int n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1]; 
            } else {
                dp[i][j] = std::min(dp[i - 1][j - 1], std::min(dp[i][j - 1], dp[i - 1][j])) + 1;
            }
        }
    }
    return dp[m][n];
}

选择树节点

这个算是树形dp里面最简单的一个了。有一棵树，每个节点有一个值。从中选出若干节点，使它们值的和最大，要求如果一个节点被选，那么它的子节点不能选。

做法就是记录每个节点选或不选的最优解，后续遍历的同时进行 DP。

void dfs(int root)
{
    dp[root][0] = 0;
    dp[root][1] = weight[root];
    for(int i = 0; i < v[root].size(); i++) {
        int k = v[root][i];
        dfs(k);
        dp[root][1] += dp[k][0];
        dp[root][0] += max(dp[k][0], dp[k][1])；
    }
}

重新学算法(2)——动态规划

2018/11/03 ・学习