Dynamic Programming

动态规划的由来

动态规划（Dynamic Programming，DP）是一种解决最优化问题的方法，它通过将复杂问题分解为更简单的子问题来求解。这种方法最早由理查德·贝尔曼（Richard Bellman）在1950年代提出，最初是用于解决决策过程中的问题，尤其是在控制论和运筹学领域。

动态规划的基本思想是利用子问题的最优解构造出原问题的最优解。它的由来可以追溯到以下几个关键点：

重叠子问题：许多最优化问题可以分解成重叠的子问题，动态规划通过记录子问题的解来避免重复计算。
最优子结构：如果一个问题的最优解包含其子问题的最优解，则可以通过解决子问题来构造原问题的解。
贝尔曼方程：贝尔曼提出了一个递归关系（即贝尔曼方程），描述了如何通过子问题的解来得到原问题的解。

动态规划的应用广泛，包括背包问题、最短路径问题、最长公共子序列等多个领域，是算法设计中一个非常重要的概念。

引入动态规划-爬楼梯问题

Question

假设你正在爬楼梯。需要爬 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶，求有多少种不同的方法爬到楼顶，我们要求算法在线性时间内解决这一问题。

如果我们要使用常规的计数方法或者分治法来计算，其时间复杂度是达不到线性时间的要求的；但是我们可以使用动态规划的方法来解决这个问题。

考虑最后一步，当我们即将到达楼顶时，我们可以选择爬 1 个台阶或者 2 个台阶。如果我们选择爬 1 个台阶，那么前面的 n-1 个台阶有多少种爬法我们已经知道了；如果我们选择爬 2 个台阶，那么前面的 n-2 个台阶有多少种爬法我们也知道了。因此，爬到第 n 阶的方法数就是爬到第 n-1 阶和第 n-2 阶的方法数之和。即：

f(n) = f(n-1) + f(n-2)

这就是斐波那契数，然而虽然这个形式是如此优美，代码也是如此简单

int fib(int n) {
    if (n <= 1) return 1; 
    return fib(n-1) + fib(n-2);
}

但是每一次计算我们都需要计算到最深再返回，这样的时间复杂度是爆炸的；我们可以使用动态规划的方法来解决这个问题，我们可以使用一个数组来保存每一步的结果，这样我们就可以在 O(n) 的时间内解决这个问题。

int fib(int n) {
    if (n <= 1) return 1;
    vector<int> dp(n+1, 0);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}

这一重要的思想我们称其为 “记忆化”，非常形象，因为我们就是利用额外的空间记住曾经算过的结果，从而避免了重复计算的问题。换句话说，原先递归的方法实际上是一种 “自顶向下” 的方法，它符合我们的直接思路：最后长度为 n 的问题需要长度为 n − 1 和 n − 2 的求和，那我们的代码直接利用递归计算递归式显得非常自然。但是重复的计算迫使我们放弃这种自然的想法，转而采用自底向上从小问题逐步迭代构建原问题的解法。

Summary

在爬楼梯这一简单而经典的问题中，通过对最后一步两种情况的分类，将整个问题的解转化为了两个子问题解的求和，即有一个从子问题的解到原问题的解的递推公式，然后我们通过记忆化的方式求解递推式。我们将上述特点抽象出来：一个问题，它的最优解可以表达为一些合适的子问题的最优解的递推关系，则我们称这一问题具有最优子结构性质(因为大问题的最优解可以直接依赖于小问题的最优解) 。然后我们求解这一递推式，通过设置好 base case（这里我们也用 basecase 指代最简单的情况，但注意这时不是递归了），然后通过记忆化的方法，使用迭代算法而非费时的递归算法避免冗余计算，得到一个时间复杂度令人满意的算法，这就是动态规划的基本想法。

动态规划基本结构

动态规划方法通常用来求解最优化问题（optimization problem）。这类问题可以有很多可行解，每个解都有一个值，我们希望寻找具有最优值（最小值或最大值）的解。我们称这样的解为问题的一个最优解（an optimal solution），而不是最优解（the optimal solution），因为可能有多个解都达到最优值。我们通常按如下 4 个步骤来设计一个动态规划算法：

刻画一个最优解的结构特征；
递归地定义最优解的值；
计算最优解的值，通常采用自底向上的方法；
利用计算出的信息构造一个最优解。

前三个步骤是动态规划算法求解问题的基础。如果我们仅仅需要一个最优解的值，而非解本身，可以忽略最后一个步骤

更精炼地，事实上动态规划就是为一个具有所谓最优子结构性质（即原问题最优解可以由子问题最优解递推得到）的最优化问题寻找一个子问题到原问题的递推式，然后用记忆化方法求解，有时候需要构造这一组解

加权独立集合问题

问题引入

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额

问题可以被抽象为

考虑一个无向图 G，其上所有点都在一条线上（这种图我们称其为路径图），每个点都有一个非负权重。我们称 G 的独立集合是指顶点互不相邻的子集（换句话说独立集合不会同时包含一条边上的两个点），然后要求解一个具有最大顶点权重和的独立集合。

简单例子

在这个图中有 8 个独立子集：

空集
四个单点集
第 1 和第 3 个点
第 1 和第 4 个点
第 2 和第 4 个点

其中最大的独立集合显然是第 2 和第 4 个点构成的集合，其权重和为 8，即小偷的最优选择是偷 2 和 4 两家，最大收益是 8。需要注意的是，题目的假设中每个顶点都有非负权重，所以最优解的顶点应当是越多越好。

为了构建出这一问题的最优子结构，我们考虑在 $n$ 个点， $n-1$ 条边构成的图 $G(V,E)$ 中最后一个点 $v_n$ 在不在解当中：

如果不在，那么问题的解就是子问题 $G_{n-1}$ 的最优解
如果在，那么问题的解就是子问题 $G_{n-2}$ 的最优解加上 $v_n$

故设前 $i$ 个点的最优加权独立集合的权重之和为 $W_i$ ，我们可以写出递推关系：

W_i = \max(W_{i-1}, W_{i-2} + w_i)

最后我们可以自底向上构建解

   array A
   A[0]=0
   A[1]=w[1]
   for i in range(2,n+1):
    A[i]=max(A[i-1],(A[i-2]+w_i))
   return A[n]

我们在 $O(n)$ 复杂度内完成了这一工作

如果我们需要重构出构成最优解有哪一些点，那么可以自顶向下根据递推式来判断当前图的最后一个点是否在解中

背包问题

背包问题是一个最最经典的动态规划问题，我们这里首先介绍最基础的背包问题，即 $0-1$ 背包问题。这一问题的描述如下：我们有 $n$ 个物品，每个物品的重量为 $s_i$ ，价值为 $v_i$ ，我们有一个容量为 $C$ 的背包，我们希望找到一个最优的装载方案，使得背包中的物品总价值最大。这一问题的特点是每个物品你要么不放进包里，要么完整的 $1$ 个放进去，因此称为 $0-1$ 背包问题。

这与加权独立集合问题略有不同

如果第 $n$ 个物品不在最优解 $S$ 中，即最优方案排除了最后一件物品，因此它可以看成仅由前 $n−1$ 个物品组成的子问题的一种可行解决方案
如果第 $n$ 个物品在最优解 $S$ 中，这种情况只有在 $s_n \leqslant C$ 时才有意义。类似于加权独立集合问题，我们希望 $S − \{n\}$ 是前 $n − 1$ 个物品组成的子问题的最优解，但这显然是错误的！如果 $S − \{n\}$ 就已经把 $W$ 几乎占满，那最后 $n$ 根本就放不进来了。因此我们需要对子问题的设置略做调整： $S − \{n\}$ 应当是前 $n$ 个物品在背包容量为 $C −s_n$ 的情况下的最优解！因为我们知道 $n$ 在解中，那么除去 $n$ 之外的其它解的重量之和最多就是 $C − s_n$ ，因此 $S − \{n\}$ 应当是前 $n$ 个物品在背包容量为 $C − s_n$ 的情况下的可行解

所以

V_{i,c} = \begin{cases} V_{i-1,c}, & \text{if } s_i > c \\ \max(V_{i-1,c}, V_{i-1,c-s_i} + v_i), & \text{if } s_i \leq c \end{cases}

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for c in range(capacity + 1):
            if weights[i] > c: #如果当前物品的重量大于背包容量,不用再考虑
                dp[i][c] = dp[i-1][c]
            else:
                dp[i][c] = max(dp[i-1][c], dp[i-1][c-weights[i-1]] + values[i-1])

    return dp[n][capacity]

解的重构

矩阵乘法的计算顺序

我们考虑矩阵链相乘 $M_1M_2 \cdots M_n$ ，每个矩阵的大小为 $r_{i-1} \times r_i$ 。记

[ M_{ij} = M_iM_{i+1} \cdots M_j ]

显然前面的三个问题给我们了不少的经验：我们应当考虑最后一个矩阵，然后依据这一矩阵可能的相乘方式划分最优解的可能性。很简单的，第一种情况对应我们的计算方式是 $M_{1,n-1} \cdots M_n$ ，即先用算前 $n-1$ 个矩阵相乘的最优方式计算前 $n-1$ 个矩阵的乘积，最后与 $M_n$ 相乘；第二种情况的计算方式是 $M_{1,n-2} \cdots M_{n-1}M_n$ ，即先用算前 $n-2$ 个矩阵相乘的最优方式计算前 $n-2$ 个矩阵的乘积，最后与 $M_{n-1}M_n$ 的结果相乘。这是根据我们前面的问题的经验得到的，和表述完全一致，但事实上真的只有这两种情况吗？显然不是的！注意，请回到我们分类的根源来看：我们此时分类的依据是 $M_n$ 的计算方式，那么对于如下乘积形式：

[ M_{1,i}M_{i+1,n-1}M_n ]

只要是不同的 $i$ ，我们就可以得到不同的计算方式

因此，我们自顶向下寻找最优解时，应该考虑对于一个无序矩阵，我们的第一刀应该切在哪个地方

m_{1n} = min\{m_{1i} + m_{i+1,n} + r_0r_ir_n\}

前两项代表左右子问题的解，最后一项代表合并的代价，更具体的，我们有

m_{ij} = \begin{cases} 0, & i = j; \\ \min\limits_{i \leq k < j} \{ m_{ik} + m_{k+1,j} + r_{i-1}r_kr_j \}, & i < j. \end{cases}

void OptMatrix( const long r[ ], int N, TwoDimArray M ) 
{   int  i, j, k, L; 
    long  ThisM; 
    for( i = 1; i <= N; i++ )   M[ i ][ i ] = 0; //base case
    for( k = 1; k < N; k++ ) /* k = j - i */ 
        for( i = 1; i <= N - k; i++ ) { /* For each position */ 
	j = i + k;    M[ i ][ j ] = Infinity; 
	for( L = i; L < j; L++ ) { 
	    ThisM = M[ i ][ L ] + M[ L + 1 ][ j ] 
		    + r[ i - 1 ] * r[ L ] * r[ j ]; 
	    if ( ThisM < M[ i ][ j ] )  /* Update min */ 
		M[ i ][ j ] = ThisM; 
	}  /* end for-L */
    }  /* end for-Left */
}

代码解释

参数: r 是矩阵链的维度数组，N 是矩阵链的长度，M 是动态规划的结果表。
初始化base case：
- for( i = 1; i <= N; i++ ) M[ i ][ i ] = 0;
- 这一步将矩阵 M 的对角线元素设为 0，因为单个矩阵的乘法代价为零。
填充动态规划表：
- for( k = 1; k < N; k++ )：k 表示当前考虑的矩阵链长度。
- for( i = 1; i <= N - k; i++ )：i 是链的起始位置。
  - j = i + k;：j 是链的结束位置。
  - M[ i ][ j ] = Infinity;：初始化 M[i][j] 为无穷大，表示尚未计算出最小代价。
  - for( L = i; L < j; L++ )：L 是可能的分割点。
    - ThisM = M[ i ][ L ] + M[ L + 1 ][ j ] + r[ i - 1 ] * r[ L ] * r[ j ];
      - 计算从 i 到 L 和从 L+1 到 j 的乘法代价，加上合并两个结果矩阵的代价。
    - if ( ThisM < M[ i ][ j ] ) M[ i ][ j ] = ThisM;
      - 如果计算出的代价小于当前存储的代价，则更新 M[i][j]。

时间复杂度： $O(n^3)$ ，其中 $n$ 是矩阵链的长度。

解的重构

这一问题重构解的方法如果用和前面的问题一样简单直接的控制方法显然会比较耗时，因为我们每次要比较很多种可能的情况才能重构出解，所以我们需要做一些优化。优化的方法也非常自然，实际上关键就是用一个二维数组记住每个子问题

m_{ij} = \min\limits_{i \leq k < j} \{ m_{ik} + m_{k+1,j} + r_{i-1}r_kr_j \}

对应的最优的分点，然后当我们算出问题 $m_n$ 的最优解及其对应的最优分点后，我们再按左右两半子问题的最优分点，以此类推，用中序遍历的思想将分点输出即可，只需线性时间。

// Function to print the optimal parenthesization
void printOptimalParens(vector<vector<int>>& s, int i, int j) {
    if (i == j) {
        cout << "A" << i;
    } else {
        cout << "(";
        printOptimalParens(s, i, s[i][j]);
        cout << s[i][j];
        printOptimalParens(s, s[i][j] + 1, j);
        cout << ")";
    }
}

最优二叉搜索树

Question

这一问题给定如下输入：给定一列单词 $w_1, w_2, \ldots, w_n$ （它们的顺序已经按字典序排列）和它们出现的固定的概率 $p_1, p_2, \ldots, p_n$ 。问题是要以一种方法在一棵二叉查找树中安放这些单词使得总的期望查找时间最小。

在一棵二叉查找树中，访问深度 $d$ 处的每一个元素所需要的比较次数是 $d+1$ ，因此如果 $w_i$ 被放在深度 $d_i$ 上，那么我们期望将 $\sum_{i=1}^{N} p_i (1 + d_i)$ 极小化。

使用贪心和AVL等算法不一定可行，使用分治法又需要首先知道最优根节点在哪里，所以我们使用动态规划的方法来解决这个问题。

如果我们知道最优根节点 $w_k$ ,那么在整个问题的最优解中，由于事先已经按照字母序排好，左子树必然是 $w_1 \cdots w_{k-1}$ 的最优解，右子树也必然是 $w_{k+1} \cdots w_n$ 的最优解，因此我们可以得到递推关系

c_{ij} = \sum_{k=i}^{j} p_k + \min\limits_{i \leqslant k \leqslant j} \{ c_{i,k-1} + c_{k+1,j} \}, \quad i \leqslant j.

其中 $p_k$ 代表权重， $c_{ij}$ 代表从 $i$ 到 $j$ 的最优成本， $c_{i,k-1}$ 代表左子树的最优成本， $c_{k+1,j}$ 代表右子树的最优成本。

前面第一项是因为由于根节点的存在，所有的节点都加深一层，是两个子问题结合的结果，后面的项是左右子树的最优解。

这个算法是 $O(n^3)$ 的，但是可以优化到 $O(n^2)$