自律小屋

Appearance

当前页大纲

动态规划解题框架 ​

动态规划是算法与数据结构的重难点之一，其包含了「分治思想」、「空间换时间」、「最优解」等多种基石算法思想，常作为笔面试中的中等困难题出现。为帮助读者全面理解动态规划，知晓其来龙去脉，本文将从以下几个角度切入介绍：

  1. 动态规划问题特点，动态规划和分治算法的联系与区别；
  2. 借助例题介绍重叠子问题和最优子结构分别是什么，以及动态规划是如何解决它们的；
  3. 动态规划的解题框架总结；
  4. 动态规划的练习例题，从易到难排序；

动态规划特点 ​

「分治」是算法中的一种基本思想，其通过将原问题分解为子问题，不断递归地将子问题分解为更小的子问题，并通过组合子问题的解来得到原问题的解。

类似于分治算法，「动态规划」也通过组合子问题的解得到原问题的解。不同的是，适合用动态规划解决的问题具有「重叠子问题」和「最优子结构」两大特性。

重叠子问题 ​

动态规划的子问题是有重叠的，即各个子问题中包含重复的更小子问题。若使用暴力法穷举，求解这些相同子问题会产生大量的重复计算，效率低下。

动态规划在第一次求解某子问题时，会将子问题的解保存；后续遇到重叠子问题时，则直接通过查表获取解，保证每个独立子问题只被计算一次，从而降低算法的时间复杂度。

最优子结构 ​

如果一个问题的最优解可以由其子问题的最优解组合构成，并且这些子问题可以独立求解，那么称此问题具有最优子结构。

动态规划从基础问题的解开始，不断迭代组合、选择子问题的最优解，最终得到原问题最优解。

重叠子问题示例：斐波那契数列 ​

斐波那契数形成的数列为 $[0, 1, 1, 2, 3, 5, 8, 13, \cdots]$ ，数学定义如下： $$ \begin{aligned} & F_0 = 0 \ & F_1 = 1 \ & F_n = F_{n-1} + F_{n-2} \end{aligned} $$ 题目： 求取第 $n$ 个斐波那契数（从第 0 个斐波那契数开始）。

以下，本文从「暴力递归」$\rightarrow$「记忆化递归」$\rightarrow$「动态规划」三种解法，介绍重叠子问题的概念与解决方案。

方法一：暴力递归 ​

设斐波那契数列第 $n$ 个数字为 $f(n)$ 。根据数列定义，可得 $f(n) = f(n - 1) + f(n - 2)$ ，且第 0 , 1 个斐波那契数分别为 $f(0) = 0$ , $f(1) = 1$ 。

我们很容易联想到使用分治思想来求取 $f(n)$ ，即将求原问题 $f(n)$ 分解为求子问题 $f(n-1)$ 和 $f(n-2)$ ，向下递归直至已知的 $f(0)$ 和 $f(1)$ ，最终组合这些子问题求取原问题 $f(n)$ 。

Python
# 求第 n 个斐波那契数
def fibonacci(n):
    if n == 0: return 0 # 返回 f(0)
    if n == 1: return 1 # 返回 f(1)
    return fibonacci(n - 1) + fibonacci(n - 2) # 分解为两个子问题求解
Java
// 求第 n 个斐波那契数
int fibonacci(int n) {
    if (n == 0) return 0; // 返回 f(0)
    if (n == 1) return 1; // 返回 f(1)
    return fibonacci(n - 1) + fibonacci(n - 2); // 分解为两个子问题求解
}
C++
int fibonacci(int n) {
    if (n == 0) return 0; // 返回 f(0)
    if (n == 1) return 1; // 返回 f(1)
    return fibonacci(n - 1) + fibonacci(n - 2); // 分解为两个子问题求解
}

Picture1.png

如上图所示，为暴力递归求斐波那契数 $f(5)$ 形成的二叉树，树中的每个节点代表着执行了一次 fibonacci() 函数，且有：

  • 执行一次 fibonacci() 函数的时间复杂度为 $O(1)$ ；
  • 二叉树节点数为指数级 $O(2^n)$ ；

因此，暴力递归的总体时间复杂度为 $O(2^n)$ 。此方法效率低下，随着 $n$ 的增长产生指数级爆炸。

方法二：记忆化递归 ​

观察发现，暴力递归中的子问题多数都是重叠子问题，即：

$$ \begin{aligned} & f(n) = f(n - 1) + f(n - 2) & 包含 f(n - 2) \ & f(n - 1) = f(n - 2) + f(n - 3) & 重复 f(n - 2) \ & f(n - 2) = f(n - 3) + f(n - 4) & 重复 f(n - 3) \ & \cdots &以此类推 \end{aligned} $$

这些重叠子问题产生了大量的递归树节点，其不应被重复计算。实际上，可以在递归中第一次求解子问题时，就将它们保存；后续递归中再次遇到相同子问题时，直接访问内存赋值即可。记忆化递归的代码如下所示。

Python
def fibonacci(n, dp):
    if n == 0: return 0           # 返回 f(0)
    if n == 1: return 1           # 返回 f(1)
    if dp[n] != 0: return dp[n]   # 若 f(n) 以前已经计算过，则直接返回记录的解
    dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp) # 将 f(n) 则记录至 dp
    return dp[n]

# 求第 n 个斐波那契数
def fibonacci_memorized(n):
    dp = [0] * (n + 1) # 用于保存 f(0) 至 f(n) 问题的解
    return fibonacci(n, dp)
Java
int fibonacci(int n, int[] dp) {
    if (n == 0) return 0;           // 返回 f(0)
    if (n == 1) return 1;           // 返回 f(1)
    if (dp[n] != 0) return dp[n];   // 若 f(n) 以前已经计算过，则直接返回记录的解
    dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp); // 将 f(n) 则记录至 dp
    return dp[n];
}


// 求第 n 个斐波那契数
int fibonacciMemorized(int n) {
    int[] dp = new int[n + 1]; // 用于保存 f(0) 至 f(n) 问题的解
    return fibonacci(n, dp);
}
C++
int fibonacci(int n, vector<int> dp) {
    if (n == 0) return 0;           // 返回 f(0)
    if (n == 1) return 1;           // 返回 f(1)
    if (dp[n] != 0) return dp[n];   // 若 f(n) 以前已经计算过，则直接返回记录的解
    dp[n] = fibonacci(n - 1, dp) + fibonacci(n - 2, dp); // 将 f(n) 则记录至 dp
    return dp[n];
}


// 求第 n 个斐波那契数
int fibonacciMemorized(int n) {
    vector<int> dp(n + 1, 0); // 用于保存 f(0) 至 f(n) 问题的解
    return fibonacci(n, dp);
}

如下图所示，应用记忆化递归方法后，递归树中绝大部分节点被剪枝。此时，fibonacci() 函数的调用次数从 $O(2^n)$ 指数级别降低至 $O(n)$ 线性级别，时间复杂度大大降低。

Picture2.png

方法三：动态规划 ​

递归本质上是基于分治思想的从顶至底的解法。借助记忆化递归思想，可应用动态规划从底至顶求取 $f(n)$ ，代码如下所示。

Python
# 求第 n 个斐波那契数
def fibonacci(n):
    if n == 0: return 0       # 若求 f(0) 则直接返回 0
    dp = [0] * (n + 1)        # 初始化 dp 列表
    dp[0], dp[1] = 0, 1       # 初始化 f(0), f(1)
    for i in range(2, n + 1): # 状态转移求取 f(2), f(3), ..., f(n) 
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]              # 返回 f(n)
Java
// 求第 n 个斐波那契数
int fibonacci(int n) {
    if (n == 0) return 0;          // 若求 f(0) 则直接返回 0
    int[] dp = new int[n + 1];     // 初始化 dp 列表
    dp[1] = 1;                     // 初始化 f(0), f(1)
    for (int i = 2; i <= n; i++) { // 状态转移求取 f(2), f(3), ..., f(n) 
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];                  // 返回 f(n)
}
C++
// 求第 n 个斐波那契数
int fibonacci(int n) {
    if (n == 0) return 0;          // 若求 f(0) 则直接返回 0
    vector<int> dp(n + 1, 0);      // 初始化 dp 列表
    dp[1] = 1;                     // 初始化 f(0), f(1)
    for (int i = 2; i <= n; i++) { // 状态转移求取 f(2), f(3), ..., f(n) 
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];                  // 返回 f(n)
}

如下图所示，为动态规划求解 $f(5)$ 的迭代流程，其是转移方程 $f(n) = f(n - 1) + f(n - 2)$ 的体现。

Picture3.png

上述动态规划解法借助了一个 dp 数组保存子问题的解，其空间复杂度为 $O(N)$ 。而由于 $f(n)$ 只与 $f(n - 1)$ 和 $f(n - 2)$ 有关，因此我们可以仅使用两个变量 $a$ , $b$ 交替前进计算即可。此时动态规划的空间复杂度降低至 $O(1)$ ，代码如下所示。

Python
# 求第 n 个斐波那契数
def fibonacci(n):
    if n == 0: return 0       # 若求 f(0) 则直接返回 0
    a, b = 0, 1               # 初始化 f(0), f(1)
    for i in range(2, n + 1): # 状态转移求取 f(2), f(3), ..., f(n) 
        a, b = b, a + b
    return b                  # 返回 f(n)
Java
// 求第 n 个斐波那契数
int fibonacci(int n) {
    if (n == 0) return 0;           // 若求 f(0) 则直接返回 0
    int a = 0, b = 1;               // 初始化 f(0), f(1)
    for (int i = 2; i <= n; i++) {  // 状态转移求取 f(2), f(3), ..., f(n) 
        int tmp = a;
        a = b;
        b = tmp + b;
    }
    return b;                       // 返回 f(n)
}
C++
// 求第 n 个斐波那契数
int fibonacci(int n) {
    if (n == 0) return 0;           // 若求 f(0) 则直接返回 0
    int a = 0, b = 1;               // 初始化 f(0), f(1)
    for (int i = 2; i <= n; i++) {  // 状态转移求取 f(2), f(3), ..., f(n) 
        int tmp = a;
        a = b;
        b = tmp + b;
    }
    return b;                       // 返回 f(n)
}

示例小结 ​

记忆化递归和动态规划的本质思想是一致的，是对斐波那契数列定义的不同表现形式：

  • 记忆化递归 — 从顶至低： 求 $f(n)$ 需要 $f(n - 1)$ 和 $f(n - 2)$ ； $\cdots$ ；求 $f(2)$ 需要 $f(1)$ 和 $f(0)$ ；而 $f(1)$ 和 $f(0)$ 已知；
  • 动态规划 — 从底至顶： 将已知 $f(0)$ 和 $f(1)$ 组合得到 $f(2)$ ；$\cdots$ ；将 $f(n - 2)$ 和 $f(n - 1)$ 组合得到 $f(n)$ ；

斐波那契数列问题不包含「最优子结构」，只需计算每个子问题的解，避免重复计算即可，并不需要从子问题组合中选择最优组合。接下来，本文借助「最高蛋糕售价方案」，介绍动态规划的最优子结构概念。

最优子结构示例：蛋糕最高售价 ​

小力开了一家蛋糕店，并针对不同重量的蛋糕设定了不同售价，分别为：

蛋糕重量0123456
售价023671115

问题： 现给定一个重量为 $n$ 的蛋糕，问小力应该如何切分蛋糕，达到最高的蛋糕总售价。

设重量为 $n$ 蛋糕的售价为 $p(n)$ ，切分的最高总售价为 $f(n)$ 。

  • 子问题： $f(n)$ 的子问题包括 $f(0), f(1), f(2), \cdots, f(n - 1)$ ，分别代表重量为 $0, 1, 2, \cdots, n - 1$ 蛋糕的最高售价。 已知无蛋糕时 $f(0) = 0$ ，蛋糕重量为 1 时不可切分 $f(1) = p(1)$ ；

  • 最优子结构：

    • 定义： 如果一个问题最优解可以由其子问题最优解组合构成，那么称此问题具有最优子结构。
    • 对于本题： 重量为 $n$ 的蛋糕的总售价可切分为 $n$ 种组合，即重量为 $0, 1, 2, ..., n - 1$ 蛋糕最高售价加上 $n, n - 1, n - 2, \cdots, 1$ 剩余重量蛋糕的售价；从这些组合中，售价最高的组合便是原问题的解 $f(n)$ ，这便是本题的最优子结构。

  • 状态转移方程： 找出最优子结构后，易构建出如下的状态转移方程。

$$ f(n) = \max_{0 \leq i < n} (f(i) + p(n - i)) $$

根据以上推导，本题也能使用「暴力递归」$\rightarrow$「记忆化递归」$\rightarrow$「动态规划」三种方法解决。

方法一：暴力递归 ​

暴力递归解法的代码如下，其时间复杂度为指数级 $O(2^n)$ 。

Python
# 输入蛋糕价格列表 price_list ，求重量为 n 蛋糕的最高售价
def max_cake_price(n, price_list):
    if n <= 1: return price_list[n] # 蛋糕重量 <= 1 时直接返回
    f_n = 0
    for i in range(n):  # 从 n 种组合种选择最高售价的组合作为 f(n)
        f_n = max(f_n, max_cake_price(i, price_list) + price_list[n - i])
    return f_n          # 返回 f(n)

max_cake_price(4, [0, 2, 3, 6, 7, 11, 15])
Java
// 输入蛋糕价格列表 priceList ，求重量为 n 蛋糕的最高售价
int maxCakePrice(int n, int[] priceList) {
    if (n <= 1) return priceList[n]; // 蛋糕重量 <= 1 时直接返回
    int f_n = 0;
    for (int i = 0; i < n; i++)      // 从 n 种组合种选择最高售价的组合作为 f(n)
        f_n = Math.max(f_n, maxCakePrice(i, priceList) + priceList[n - i]);
    return f_n;                      // 返回 f(n)
}
C++
// 输入蛋糕价格列表 priceList ，求重量为 n 蛋糕的最高售价
int maxCakePrice(int n, vector<int> priceList) {
    if (n <= 1) return priceList[n]; // 蛋糕重量 <= 1 时直接返回
    int f_n = 0;
    for (int i = 0; i < n; i++)      // 从 n 种组合种选择最高售价的组合作为 f(n)
        f_n = max(f_n, maxCakePrice(i, priceList) + priceList[n - i]);
    return f_n;                      // 返回 f(n)
}

如下图所示，为暴力递归求解 $f(4)$ 形成的多叉树。

Picture4.png

方法二：记忆化递归 ​

观察发现，递归树中存在大量重叠子问题，可通过记忆化处理避免重复计算。记忆化递归的算法的时间复杂度为 $O(n^2)$ ，包括：

  • $f(2)$ 至 $f(n)$ 共 $n - 1$ 个待计算子问题，使用 $O(n)$ 时间；
  • 计算某 $f(i)$ 需遍历 $i - 1$ 种子问题组合，使用 $O(n)$ 时间；
Python
# 输入蛋糕价格列表 price_list ，求重量为 n 蛋糕的最高售价
def max_cake_price(n, price_list, dp):
    if n <= 1: return price_list[n] # 蛋糕重量 <= 1 时直接返回
    f_n = 0
    for i in range(n):  # 从 n 种组合种选择最高售价的组合作为 f(n)
        # 若 f(i) 以前已经计算过，则调取记录的解；否则，递归计算 f(i)
        f_i = dp[i] if dp[i] != 0 else max_cake_price(i, price_list, dp)
        f_n = max(f_n, f_i + price_list[n - i])
    dp[n] = f_n         # 记录 f(n) 至 dp 数组
    return f_n          # 返回 f(n)

def max_cake_price_memorized(n, price_list):
    dp = [0] * (n + 1)
    return max_cake_price(n, price_list, dp)
Java
// 输入蛋糕价格列表 priceList ，求重量为 n 蛋糕的最高售价
int maxCakePrice(int n, int[] priceList, int[] dp) {
    if (n <= 1) return priceList[n]; // 蛋糕重量 <= 1 时直接返回
    int f_n = 0;
    for (int i = 0; i < n; i++) {    // 从 n 种组合种选择最高售价的组合作为 f(n)
        int f_i = dp[i] != 0 ? dp[i] : maxCakePrice(i, priceList, dp);
        f_n = Math.max(f_n, f_i + priceList[n - i]);
    }
    dp[n] = f_n;                     // 记录 f(n) 至 dp 数组
    return f_n;                      // 返回 f(n)
}

int maxCakePriceMemorized(int n, int[] priceList) {
    int[] dp = new int[n + 1];
    return maxCakePrice(n, priceList, dp);
}
C++
// 输入蛋糕价格列表 priceList ，求重量为 n 蛋糕的最高售价
int maxCakePrice(int n, vector<int> &priceList, vector<int> dp) {
    if (n <= 1) return priceList[n]; // 蛋糕重量 <= 1 时直接返回
    int f_n = 0;
    for (int i = 0; i < n; i++) {    // 从 n 种组合种选择最高售价的组合作为 f(n)
        int f_i = dp[i] != 0 ? dp[i] : maxCakePrice(i, priceList, dp);
        f_n = max(f_n, f_i + priceList[n - i]);
    }
    dp[n] = f_n;                     // 记录 f(n) 至 dp 数组
    return f_n;                      // 返回 f(n)
}

int maxCakePriceMemorized(int n, vector<int> priceList) {
    vector<int> dp(n + 1, 0);
    return maxCakePrice(n, priceList, dp);
}

如下图所示，为记忆化递归求解 $f(4)$ 形成的多叉树。观察得知，重叠子问题皆被剪枝。

Picture5.png

方法三：动态规划 ​

相较于记忆化递归的从顶至底方法，易得动态规划的从底至顶方法，代码如下所示。

Python
# 输入蛋糕价格列表 price_list ，求重量为 n 蛋糕的最高售价
def max_cake_price(n, price_list):
    if n <= 1: return price_list[n] # 蛋糕重量 <= 1 时直接返回
    dp = [0] * (n + 1)              # 初始化 dp 列表
    for j in range(1, n + 1):       # 按顺序计算 f(1), f(2), ..., f(n)
        for i in range(j):          # 从 j 种组合种选择最高售价的组合作为 f(j)
            dp[j] = max(dp[j], dp[i] + price_list[j - i])
    return dp[n]
Java
// 输入蛋糕价格列表 priceList ，求重量为 n 蛋糕的最高售价
int maxCakePrice(int n, int[] priceList) {
    if (n <= 1) return priceList[n];  // 蛋糕重量 <= 1 时直接返回
    int[] dp = new int[n + 1];        // 初始化 dp 列表
    for (int j = 1; j <= n; j++) {    // 按顺序计算 f(1), f(2), ..., f(n)
        for (int i = 0; i < j; i++)   // 从 j 种组合种选择最高售价的组合作为 f(j)
            dp[j] = Math.max(dp[j], dp[i] + priceList[j - i]);
    }
    return dp[n];
}
C++
// 输入蛋糕价格列表 priceList ，求重量为 n 蛋糕的最高售价
int maxCakePrice(int n, vector<int> priceList) {
    if (n <= 1) return priceList[n];  // 蛋糕重量 <= 1 时直接返回
    vector<int> dp(n + 1, 0);         // 初始化 dp 列表
    for (int j = 1; j <= n; j++) {    // 按顺序计算 f(1), f(2), ..., f(n)
        for (int i = 0; i < j; i++)   // 从 j 种组合种选择最高售价的组合作为 f(j)
            dp[j] = max(dp[j], dp[i] + priceList[j - i]);
    }
    return dp[n];
}

如下图所示，为动态规划求解 $f(4)$ 的迭代流程，其是转移方程 $f(n) = \max_{0 \leq i < n} (f(i) + p(n - i))$ 的体现。

Picture6.png

示例小结 ​

本题同时包含「重叠子问题」和「最优子结构」，为动态规划的典型问题。动态规划通过填表避免了重复计算问题，并通过状态转移方程、初始状态实现对问题的迭代求解。

普遍来看，求最值 的问题一般都具有「重叠子问题」和「最优子结构」特点，因此此类问题往往适合用动态规划解决。

动态规划解题框架 ​

若确定给定问题具有重叠子问题和最优子结构，那么就可以使用动态规划求解。总体上看，求解可分为四步：

  1. 状态定义： 构建问题最优解模型，包括问题最优解的定义、有哪些计算解的自变量；
  2. 初始状态： 确定基础子问题的解（即已知解），原问题和子问题的解都是以基础子问题的解为起始点，在迭代计算中得到的；
  3. 转移方程： 确定原问题的解与子问题的解之间的关系是什么，以及使用何种选择规则从子问题最优解组合中选出原问题最优解；
  4. 返回值： 确定应返回的问题的解是什么，即动态规划在何处停止迭代；

完成以上步骤后，便容易写出对应的解题代码。

示例：斐波那契数列 ​

  • 状态定义：一维 $dp$ 列表，设第 $i$ 个斐波那契数为 $dp[i]$ ；
  • 初始状态：已知第 $0$ , $1$ 个斐波那契数分别为 $dp[0] = 0$ , $dp[1] = 1$ ；
  • 转移方程：后一个数字等于前两个数字之和，即

$$ dp[i] = dp[i - 1] + dp[i - 2] $$

  • 返回值：需求取的第 $n$ 个斐波那契数 $dp[n]$ ；

示例：蛋糕最高售价 ​

  • 状态定义：一维 $dp$ 列表，设重量为 $i$ 蛋糕的售价为 $p(i)$ ，重量为 $i$ 蛋糕切分后的最高售价为 $dp[i]$ ；
  • 初始状态：已知重量为 0 蛋糕的最高售价为 0 ，重量为 1 的蛋糕最高售价为 $p(1)$ ；
  • 转移方程：$dp[n]$ 为 $n$ 种切分组合中的最高售价组合，即

$$ dp[n] = \max_{0 \leq i < n} (dp[i] + p(n - i)) $$

  • 返回值：需求取的重量为 $n$ 的蛋糕最高售价 $dp[n]$ ；

例题练习 ​

动态规划的问题种类多，难度跨度较大，需要充足练习、熟能生巧。以下给出若干典型例题，供读者巩固理解本文内容。

题目难度描述
跳跃训练简单与本文的斐波那契数列例题等价
连续天数的最高销售额简单求最大值问题，关键点在于状态定义
珠宝的最高价值简单求最大值问题，特点是其 $dp$ 列表是二维的
统计结果概率中等容易想到暴力枚举方法，难点为列出状态转移方程，且正向递推方法比较 tricky
模糊搜索验证困难状态定义容易得出，但状态转移方程复杂、选择规则分支多

MIT License.

Copyright © 2024 自律小屋