算法-动态规划(一)

概述

动态规划 与分治法类似，皆是通过组合子问题解来求解原问题，二者不同点在于前者适用于子问题重叠场景，后者适用于子问题不重叠场景。正是由于存在子问题重叠，故而动态规划借助表格存储子问题解，通过多阶段决策以逐步组合得到原问题解。

动态规划所能求解的问题常具有如下三大特征：

• 最优子结构

  原问题解一定可由子问题解组合得到，换言之，通过组合子问题解一定可得到原问题的解。

• 重叠子问题

  不同子问题之间存在公共子子问题。

• 无后效性

  假定当前问题 A 由子问题 B 和 C 组成。无后效性指的是：求得 B、C 问题解后，A 问题求解过程中所使用到的决策不会对 B、C 问题解存在影响。

动态规划求解过程主要涉及三个部分：

• 状态表示

  我们使用表格存储子问题解，那么状态表示指代表格中任意一格的具体含义是什么。例如，$f[i][j]$ 表示 xxx。

• 状态转移

  状态转移指代一个子问题解应当根据哪些子问题解组合得到且以何种方式组合得到。例如，$f[i][j] = min(f[i - 1][j], f[i - 1][j - 1])$。

• 状态初始化

  为得到原问题解，首先需要初始化相关子问题解，这样通过逐步递推将会得到原问题解。例如：$f[0][0] = 0$。

动态规划求解过程看似简单，实际上没有比较多的积累是很难想到解法的。由于不是专业竞赛选手，故而我们只要简单了解一些动态规划题型就可以了。

本文之中，我们将简要介绍动态规划的两种实现方式，并比较二者区别。接下来几篇文章中，我们将进一步针对不同动态规划类型进行介绍，这些类型具体包括 —— 线性 DP (它所含内容比较多，主要介绍数字三角形模型和最长上升子序列模型)、背包 DP、状态机 DP、状态压缩 DP、区间 DP、树形 DP、数位 DP、DAG 上 DP。

实现

动态规划有两种实现方式 —— 递归和递推。

递归采用自顶向下方式进行实现。在该种实现方式中，为求得当前问题解，就需要递归求解子问题，随后基于子问题解组合得到当前问题解。由于存在子问题重叠，故而实现过程中需要使用公共空间存储子问题解 (正是由于使用公共空间存储子问题解，该种实现方式又称为 记忆化搜索)。

其实现代码大致如下：

// 公共空间(默认初始化为-1，表明该子问题尚未被求解)。
int f[i][j];

// 记忆化搜索。
void dfs(int i, int j) {
    if (f[i][j] != -1) {
        return f[i][j];
    }
    
    // 状态转移部分，首先求解子问题解，随后组合得到当前问题解。
    ...
     
    return ;
}

递推采用自底向上方式进行实现。在该种实现方式中，按照表格顺序依次求解各个子问题解即可。

其实现代码大致如下：

// 表格。
int f[i][j];

for (int i = 0; i < f.length; i++) {
    for (int j = 0; j < f[i].length; j++) {
        // 状态转移部分。
        ...
    }
}

// 原问题解就在f[i][j]之中，返回相应值即可。
return f[][];

既然存在两种实现方式，自然需要进行比较一番：

• 两种方式往往可以自由转换。通常情况下，递推实现动态规划比较简单；而在某些情况下，递归实现动态规划比较简单。针对具体题目，选择方便实现的方式即可。
• 由于递归本身具有搜索特性，故而递归方式可使用剪枝以避免无效搜索 (换言之，可优化时间复杂度)，但是它无法对空间进行优化。
• 递推方式无法对时间进行优化，但是基于滚动数组等方式可大大优化空间复杂度。