动态规划

什么是动态规划

来自维基百科的定义：动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

也就是说，动态规划是一种用来解决一类最优化问题的算法思想和策略，并不是一种具体的算法。

动态规划涉及的主题挺多的，下面是其中一些常见的：

子集求和（Subset Sum），如：最大部分连续和
最长递增子序列（LIS：Longest Increasing Subsequence）问题
最长公共子序列（LCS：Longest Common Subsequence）问题
最长回文子序列（LPS：Longest Palindrome Subsequence）问题
有向无环图（DAG）中的最长路径
编辑距离问题（Edit Distance Problem）
背包问题（Knapsack Problem）
棒材切割问题（Rod Cutting Problem）
硬币找零问题（Coin Change Problem）

下面我们通过大家比较熟悉的例子来看看动态规划这种算法思想。

![[8201717306909_.pic.jpg]]

再看 Fibonacci 数列

再来看看经典的 Fibonacci 数列问题：给一个正整数 n，寻找 Fibonacci 数列的第 n 项数字是多少？

斐波那契数以递归的方法来定义，其数学表达如下所示：

$\begin{cases} & F_0=0 \\ & F_1=1 \\ & F_n=F_{n-1} + F_{n-2}\end{cases}$

用文字来描述，就是斐波那契数列是从 0 和 1 开始，之后的斐波那契数是由之前的两数相加而得。

从第 1 项开始，斐波那契数列前几项依次是：

1，1，2，3，5，8，13，21，...

需要注意的是，斐波那契数列中，0 是第零项，而不是第一项

我们之前通常是用递归去完成的，代码如下：

#include <bits/stdc++.h>
using namespace std;

int fib(int n) {
  if (n == 0 || n == 1) return n;
  else return fib(n - 1) + fib(n - 2);
}

int main() {
  int n;
  cin >> n;

  cout << fib(n);
  return 0;
}

递归的方式很好理解，实现也非常简单，但算法效率却有点问题。

以 fib(4) 为例：

由于每次调用 fib 函数都会产生两次额外 fib 函数调用，该解法的算法复杂度是 $O(2^n)$ ，当输入的 $n$ 越大，函数的运行速度就越慢，算法的执行效率很低。

另外，在求解的过程中，很多同样 fib 函数被调用了多次，比如：fib(2) 求了两次，fib(1) 求了三次，fib(0) 也求了两次，这次重复的计算也会影响效率，实际上没必要的。

我们来看看如何改进来，直观能想到的是把第一次求出的 fib(n) 结果保存下来，如果下次需要再用到，则直接拿出来用，而不是重新计算。

下面按照这个思路改进后的代码如下：

#include <bits/stdc++.h>
using namespace std;

int dp[100]; // 假设我们最多求 fibonacci 数列第 100 项

int fib(int n) {
  if (dp[n] != 0) return dp[n];
  if (n == 0 || n == 1) return n;

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

int main() {
  int n;
  cin >> n;

  cout << fib(n);
  return 0;
}

通过数组来存放每次计算的结果。经过改进后，由于每个 fib() 只计算一次，算法的时间复杂度从 $O(2^n)$ 降为 $O(n)$ ，这也是正是动态规划（dynamic programming）编程带来的好处。

而刚刚这种通过缓存子问题结果的方法被称为记忆化（memoization），这正是动态规划问题求解的一种实现方式：自顶向下（递归 + 记忆化），从原问题开始递归求解，每当遇到子问题时，先检查是否已经求解过，若是则直接返回结果，否则计算并保存结果。

动态规划的基本思路

什么时候用 DP

从上面 Fibonacci 的例子可以观察到一些可以应用 DP 来解决问题的特征。

首先，在求解问题 fib(n) 时，需要求解下面的一些子问题 fib(n - 1) 和 fib(n - 2)，而且这些子问题往往被重复计算了多次，这通常被称为「重叠子问题」。

通过计算子问题的最优结果，可以得到原始问题的最优结果，这样的子问题结构被称为「最优子结构」。

重叠子问题与最优子结构也是我们判断一个问题是否可以通过动态规划来解决的关键所在。

通常来说，动态规划问题（DP Problem）求解有两种实现方式，一种自顶向下（Top-Down），一种自底向上（Bottom-Up）。

下面我们分别来看看。

自顶向下 DP

前面我们经过改进后求 Fibnacci 数列第 n 项的递归方法就是用的自顶而下的 DP 求解。

自顶向下 DP 一般是通过改进递归来实现的，避免重复计算相同子问题的一种方法就是缓存这些子问题的结果（维护一个已计算的值表）。

如果缓存中包含当前要求的某个输入的结果，则直接从缓存中返回该值。
否则，计算并将结果存入缓存，当下次需要解决同样的子问题时，就不需要再计算，直接从缓存拿结果。

这种通过缓存子问题结果的方法也被称为记忆化（memoization），通过记忆化手段可以消除许多递归调用。

通过缓存子问题结果，我们的算法时间复杂度降到 $O(n)$ ；另外，要求 fib(n)，我们需要计算 fib(n-1) 和 fib(n-2)，一直到 fib(1) 和 fib(0)，这意味着我们的空间复杂度也为 $O(n)$ 。

我们再来看看是否还可以优化？

在整个计算的过程中，每个子问题都取决于紧接其后的两个子问题，而不取决其它的子问题。例如，要计算 fib(5)，只需要 fib(4) 和 fib(3) 的结果就行。

按照这个思路，在计算过程中，我们只需要保留三个值，当前值和前两项的值，其它不需要的值都可以丢弃。

经过再次改进的代码如下：

#include <bits/stdc++.h>
using namespace std;

int fib(int n) {
  if (n == 0 || n == 1) return n;
  int a = 1, b = 1, c;
  for (int i = 3; i <= n; i++) {
    c = a + b;
    a = b;
    b = c;
  }
  return b;
}

int main() {
  int n;
  cin >> n;

  cout << fib(n);
  return 0;
}

最终改进后的版本，时间复杂度仍然是 $O(n)$ ，空间复杂度是恒定的，不再随输入的大小而增大，因此空间复杂度为 $O(1)$ ，相比我们最初的普通递归版本，效率已大大提升！

如果解决一个问题的办法是先解「较小」的子问题，再逐步解决更大的问题，这种方法就被称为自

自底向上 DP

自底向上 DP 一般是通过迭代来解决，

#include <iostream>
using namespace std;

const int MAXN = 100;
int f[MAXN];

void fib() {
    // 初始化边界条件
    f[0] = 0;
    f[1] = 1;

    // 状态转移方程
    for (int i = 2; i < MAXN; ++i) {
        f[i] = f[i - 1] + f[i - 2];
    }

    // 输出结果
    for (int i = 0; i < MAXN; ++i) {
        cout << f[i] << " ";
    }
}

int main() {
    fib();
    return 0;
}

以上代码中，f[i] 表示斐波那契数列的第 i 项。我们使用动态规划的方法，通过状态转移方程和边界条件，避免了重复计算，从而高效地求解了斐波那契数列问题。

使用 “自底而上” 的方法，只需要保留当前计算所需的子问题的解，而在“自顶而下“的方法中，需要保存所有子问题的解。

对于求 Fibonacci 数例第 n 项这个示例来说，”自底而上“只需要保留前两个数字的值，因此空间复杂度从 $O(n)$ 降低到 $O(1)$ 。

动态规划使用场景

当一个问题拥有重叠子问题和最优子结构时，才能使用动态规划去求解。

什么是重叠子问题？

什么是最优子结构？

理解了上述使用场景，我们就可以把动态规划与贪心、分治这样的算法思想区分开来了。

动态规划与贪心：

【补充】

动态规划与分治：

【补充】

动态规划求解基本步骤

状态定义：明确问题的状态，并确定状态之间的关系。
定义状态转移方程：找到状态之间的关系，即当前状态是如何由之前的状态推导出来的。
确定边界条件：确定状态转移方程的初始状态，即边界条件。
计算顺序：确定状态的计算顺序，以避免重复计算。

在求解动态规划相关的问题时，如何识别和定义状态和状态转移方程是核心，也是最难的部分。

在下面的示例中，大家尤其要注意，我们是如何通过分析去得出状态和状态转移方程的。

[[2024-04-29_solution_1589-最大连续部分和]] 连续
[[2024-04-29_solution_1794-最长不下降子序列（LIS）]] 不连续

0-1 背包问题

1282 - 简单背包问题-Dailyup OJ (cocoet.cn)

![[CleanShot 2024-05-06 at 13.20.51.png]]

简单背包问题，也称为0/1背包问题，是一个经典的动态规划问题。在这个问题中，你给定一组物品，每个物品都有一个重量和一个价值，同时给定一个背包的容量限制。目标是选择一组物品放入背包中，以使得背包中物品的总价值最大，但背包的总重量不超过容量限制。

需要注意的是，在简单背包问题中，每件物品是唯一的（只有一件，要么选，要么不选），这也正是 0 / 1 背包名称的由来。

问题描述

假设有 n 个物品，每个物品 i 有对应的价值 v[i] 和重量 w[i]。背包的容量限制为 W。

动态规划解法

状态定义

我们定义 dp[i][j] 表示考虑前 i 个物品，在不超过容量 j 的情况下，我们能得到的最大价值。

状态转移方程

对于每个物品 i 和每个容量 j，我们有两种选择：

不能装下第 i 个物品，那么 dp[i][j] = dp[i - 1][j]。
能装下第 i 个物品，又有两种选择，选其中最大价值的一种
- 不选择，那么同样 dp[i][j] = dp[i - 1][j]
- 选择，那么 dp[i][j] = dp[i - 1][j - w[i]] + v[i]。

最终状态转移方程为：

不能装下：dp[i][j] = dp[i - 1][j]
能装下：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])

初始状态

dp[0][j] = 0 对于所有的 j，因为没有物品时背包的价值为0。

边界条件

dp[i][0] = 0 对于所有的 i，因为当背包容量为0时，不论选择哪些物品，背包的价值都为0。

计算顺序

按物品顺序 i 从 1 到 n，按容量 j 从 1 到 W 进行计算。

问题分析

![[04. Approach 1 Recursion.mp4 - 01.41.900.png]]

![[04. Approach 1 Recursion.mp4 - 12.37.966 1.png]]

解决动态规划的问题，有多种方法，通常来说，直接找到自底而上的方法很难。一般的顺序是：

递归（Recursion）
记忆化（Memoization），自上而下（Top down）
制表（Tabulation），自底而上（Bottom up）
空间优化（Space optimization）

参考实现

// 1282 - 简单背包问题
#include <bits/stdc++.h>
using namespace std;

int maxv, n, dp[110][20010], w[110], v[110];

int main() {
  cin >> maxv >> n;

  for (int i = 1 ; i <= n; i++) {
    cin >> w[i] >> v[i];
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= maxv; j++) {
      if (w[i] <= j) {
        // 能装下，但可选，可不选
        dp[i][j] = max(dp[i-1][j], v[i] + dp[i-1][j-w[i]]);
      } else { // 不能装下
        dp[i][j] = dp[i-1][j];
      }
    }
  }

  cout << dp[n][maxv] << endl;

  return 0;
}