算法设计与分析：动态规划

发表于 2021-12-16 更新于 2021-12-28 分类于算法

算法思想

动态规划算法的有效性依赖于问题本身所具有的两个重要性质：

最优子结构

一个问题的最优解包含了其子问题的最优解，子问题的最优解可以得到该问题的最优解。所以可以利用子问题的最优解自底向上求解。
子问题重叠

在进行动态规划之前常常要先分析其递归关系式，但如果用递归解答的话，自顶向下产生的子问题并非总是新的子问题，动态规划用自底向上的方式消除了自顶向下重复计算子问题的弊端。

备忘录方法：

递归也可以存储子问题的结果至一个数组（一维或多维）中，在计算子问题时先判断该问题有没有被计算过，有的话返回结果即可，这就称为备忘录方法。备忘录方法可以达到和动态规划算法一样的复杂度，但是由于函数的递归调用消耗较大的栈空间。

但是在所有子问题中，若有一部分子问题不需要解答（剪枝），则备忘录方法更有用。

算法步骤：

分析最优解的结构：将最优解拆分为它的子问题的最优解加上当前的解，也就是把自己的问题交给规模更小的子问题。
建立递归关系：思考子问题和当前问题的转换方程。
计算最优值：根据递归关系自底向上计算最优值。
构造最优解：若有需要，在计算过程中可以记录子问题的划分方式，从而重现整个子问题分割过程。

例题

矩阵连乘问题

设有矩阵 $A_1, A_2, A_3, ..., A_n$ ，且对任意的 $1 \leq{i}< n$ , 存在 $A_i$ 与 $A_{i+1}$ 满足矩阵相乘的条件，即 $A_i$ 的列数等于 $A_{i+1}$ 的行数，求 $A_1, A_2, A_3,...,A_n$ 连乘的最少相乘次数。

基本问题

两个矩阵相乘需要进行多少次数乘

A 和 B 相乘得到的矩阵维度为

r_A \times c_B

结果矩阵 C 中（式中 $c_A$ 与 $r_B$ 是相同的）

C_{ij} = \sum^{c_A}_{k = 1}A_{ik}B_{kj}

也就是矩阵 C 中每一个元素需要进行 $c_A$ 次计算得到，所以 A 和 B 相乘需要进行数乘的次数为：

r_A \times c_B \times c_A

矩阵连乘时数乘的次数和矩阵的计算次序有关

矩阵相乘满足结合律，即：

ABC = A(BC) = (AB)C

所以矩阵连乘不一定是从左到右一直乘下去，而是可以挑其中一些矩阵先行相乘，得到的结果矩阵再参与其他运算。于是乎就存在下面这种情况：

假设

矩阵 A 维度为 a * b
矩阵 B 维度为 b * c
矩阵 C 维度为 c * d

在计算 $$ABC$$ 时

若按照 $(AB)C$ 计算，所需的数乘次数为 $acb+acd$
若按照 $A(BC)$ 计算，所需的数乘次数为 $bcd + abd$

显然，存在 $a,b,c,d$ 使得 $acb+acd \neq bcd + abd$

若此时 $a$ 非常大，则二者的差距也将随之扩大，由此可见矩阵连乘计算次序对计算量有很大的影响

分析最优解的结构

用 A[i : j] 来代表 $A_iA_{i+1}...A_j$ ，于是我们要求的便是 A[1 : n] 。

由于 n 可能比较大，我们无法从式子中直观地得出来 A [1 : n] 的最优计算次序。

若我们从 $A_k$ 和 $A_{k+1}$ 的中间将 A[1 : n] 砍成两半，那我们只需要计算 A[1 : k] 和 A[k+1 : n] 相乘，此时求 A[1 : n]便无需再考虑计算次序的问题。

在这里我们将这个问题抛给了子问题，让子问题去解决，也就是最优解包含着其子问题的最优解，这种性质称为最优子结构性质，是可以用动态规划算法求解的显著特征。
同样，对划分后的两个子式也可以应用该方法

所以，若我们要求 A[i : j]，我们要的是在 k 的范围 $i \leq k \leq j-1$ 内逐个计算两个子式的最优解（在连乘式的 j - i 个空隙里逐个划分产生子式，并让这些子式自己去寻找自己的最优解然后上交），然后再计算两个子式相乘（也就是得到 A[i : j]）需要的数乘次数，将这三项相加后结果最小的划分即为求 A[i : j] 的最佳计算次序。

动态规划也是一种分治思想（比如其状态转移方程就是一种分治），但与分治算法不同的是，分治算法是把原问题分解为若干个子问题，自顶向下求解子问题，合并子问题的解，从而得到原问题的解。动态规划也是把原始问题分解为若干个子问题，然后自底向上，先求解最小的子问题，把结果存在表格中，在求解大的子问题时，直接从表格中查询小的子问题的解，避免重复计算，从而提高算法效率。

参考：动态规划和分治法的区别

建立递归关系

根据最优解的结构，我们可以得到递归关系式如下：

设 m(i,j) 为计算 A[i : j] 的最小数乘次数
p 为记录矩阵维度的数组， $A_i$ 矩阵的维度为 $p_{i-1}\times p_i$

m(i,j)=\left\{ \begin{array}{rcl} 1 & & {i = j}\\ min(m(i,k)+m(k+1,j)+p_{i-1}p_kp_j) & & {i < j}\\ \end{array} \right.

$min(m(i,k)+m(k+1,j)+p_{i-1}p_kp_j)$ 即为求 A [i : j] 时的取最佳划分点后的数乘数目，划分点在 $A_k$ 与 $A_{k+1}$ 之间。

计算最优值

由递归方程可以写出递归程序

#include <iostream>
#include <vector>

using namespace std;

// 使用递归求解
int Recursion(const vector<int> &p, int i, int j) {
    if (i == j) {
        return 0;
    }
    // 在 k 和 k+1 间划分
    int min_times = Recursion(p, i, i) + Recursion(p, i + 1, j) + p[i-1]*p[i]*p[j];
    for (int k = i + 1; k < j; k++) {
        int times = Recursion(p, i, k) + Recursion(p, k + 1, j) + p[i - 1] * p[k] * p[j];
        if (times < min_times) {
            min_times = times;
        }
    }
    return min_times;
}

int main()
{
    int n;
    cin >> n;
    vector<int> p(n+1);
    // 输入记录矩阵维度的数组p ，矩阵 Ai 的维度为 p[i-1]*p[i]
    for (int i = 0; i <= n; i++) {
        cin >> p[i];
    }
    cout << Recursion(p, 1, n);
}

显然，简单的递归程序存在子问题重复计算的问题，如（忽略参数 p）

Recursion(3, 7) 时计算 Recursion(3, 5) 的时候会用到 Recursion(3, 4)
Recursion(2, 7) 时计算 Recursion(3, 7) 的时候会用到 Recursion(3, 4)

若可以将 Recursion(i, j) 记录下来，便可以在计算的时候直接取出来，避免重复计算：

由于函数的参数有二：i 和 j，所以很容易想到可以使用二维数组 m 来存储，m[i][j] 代表 Recursion(i, j) 的值

递归消除：

1	m[i][j] = min(m[i][k] + m[k+1][j] + p[i-1]p[k]p[j])

保证计算次序：
- 先计算 i == j 的情况
- 计算 m[i][j] ，需要计算 m[i][k] 和 m[k+1][j]，所以当要计算二维数组中的一个元素的时候，我们需要先计算他所在列的左边（也就是m[i][k]）和他同一行的元素，和他所在行的下面（不超过 j）和他同一列的元素（也就是 m[k+1][j]）的元素，所以是按一条对角线一条对角线地计算的：
  1. 初始化主对角线元素为 0；
  2. 每条斜线从左上到右下逐个元素计算，计算后依次向右上计算其他斜线；
  3. m[1][n] 即为我们想要的结果；

编写代码如下

// 使用动态规划求解
int dp(vector<int>& p, vector<vector<int>> &m, int n) {
    //主对角线
    for (int i = 1; i <= n; i++) {
        m[i][i] = 0;
    }
    
    // 遍历 n-1 条对角线
    for (int l = 1; l < n; l ++) {
        //逐行处理对角线上的元素
        for (int i = 1; i <= n - l; i++) {
            // 对角线的上的元素为 m[i][j]
            int j = i + l;
            // 遍历k可能的位置 （在 A[k] 和 A[k+1] 之间划分）
            m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
            for (int k = i + 1; k < j; k ++) {
                int times = m[i][k] + m[k+1][j] + p[i- 1] * p[k] * p[j];
                if (times < m[i][j]) {
                    m[i][j] = times;
                }
            }
        }
    }
    return m[1][n];
}

构造最优解

在动态规划的时候，新建一个与最优计算次序数组相同维度的数组 s ，s[i][j] 代表在 A[i : j] 的最优划分点(k)，添加后的代码如下：

// 使用动态规划求解 m为最优解矩阵 s为记录矩阵
int dp(vector<int>& p, vector< vector<int> > &m,vector< vector<int> > &s, int n) {
    //主对角线
    for (int i = 1; i <= n; i++) {
        m[i][i] = 0;
    }

    // 遍历 n-1 条对角线
    for (int l = 1; l < n; l ++) {
        //逐行处理对角线上的元素
        for (int i = 1; i <= n - l; i++) {
            // 对角线的上的元素为 m[i][j]
            int j = i + l;
            // 遍历k可能的位置 （在 A[k] 和 A[k+1] 之间划分）
            m[i][j] = m[i][i] + m[i + 1][j] + p[i - 1] * p[i] * p[j];
            // 记录切割的位置
            s[i][j] = i;
            for (int k = i + 1; k < j; k ++) {
                int times = m[i][k] + m[k+1][j] + p[i- 1] * p[k] * p[j];
                if (times < m[i][j]) {
                    m[i][j] = times;
                    s[i][j] = k;
                }
            }
        }
    }
    return m[1][n];
}

有了这个记录后，我们就可以通过 s 数组，逐步找到我们的划分：

A[1 : n] 划分为 A[1 : s[i][j]] A[s[i][j]+1 : j]
A[1 : s[i][j]] 划分为 A[1 : s[1][s[i][j]]] A[s[s[i][j]+1] : s[i][j]]

… 依次类推，由于划分需要等到其子问题确定后才能确定，所以使用递归算法进行回溯程序的设计，代码如下：

// 回溯
void Traceback(vector< vector<int> > &s, int i, int j) {
    if (i == j) return;
    //左
    Traceback(s, i, s[i][j]);
    //右
    Traceback(s, s[i][j]+1, j);
    cout << "A[" << i << ":" << s[i][j] << "] A[" << s[i][j] + 1 << ":" << j << "]" << endl;
}