解决 DP 问题的算法框架

动态规划问题在算法中属于复杂的问题. 然而，当你理解它的关键概念和算法框架后，解决它实际上是很简单的。

什么是动态规划 (DP) ?

动态规划（DP）是一种通过将复杂问题分解为更小的子问题从而解决它们的方法。这是一种自下而上的方法，这意味着它从解决较小的子问题开始，然后使用这些子问题的结果去得到更大问题的结果。

要解决 DP 问题，问题必须具有以下属性：

1.最优子结构：问题的最优解可以从其子问题的最优解得到。

2.重叠的子问题：问题可以分解为多次重复使用的子问题。

一个经典的问题 : 斐波那契

举个例子，当我们计算斐波那契数列的时候，我们可以使用 DP。

提示

斐波那契数列是一系列数字，其中每个数字都是前两个数字的总和，从0和1开始。顺序如下：0、1、1、2、3、5、8、13、21、34等。该序列以比萨的莱昂纳多命名，他也被称为斐波那契。1202年，他在《Liber Abaci》一书中介绍了西欧数学的顺序。

一般而言，我们通常使用递归函数来计算斐波那契数列，就像下面这样：

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

我们使用的技术并非 DP，而只是递归。

函数调用树存在多个节点，但是，多数节点是重复的。

我有一个公式：

DP = 递归(Recursion) + 备忘录(Memoization) 或者 制表(Tabulation) + 可选的其他改进

这是什么意思？

其实，备忘录和制表是用于提高动态规划算法性能的两种技术。

备忘录是一种技术，涉及将中间计算的结果存储在表格中，以便以后可以重复使用。这可以通过避免多次重新计算相同的子问题，帮助降低算法的整体时间复杂性。它是自上而下的。

另一方面，制表是一种涉及将所有子问题最终结果存储在表中的技术。这允许算法避免将解决方案重新计算到子问题，只需在表中查找预计算的结果。它是自下而上的。

备忘录和制表都可以用来加快动态规划算法。这两种技术之间的选择通常取决于正在解决的具体问题和可用内存量。

使用备忘录

为了使用备忘录，我们可以定义一个查找表 (Look-up table) 或者 缓存表 (Cache table) 去保存已经计算过的结果。我们通常使用哈希表去定义该结构。

在 C++ 中，我们将使用 std::unordered_map。

举个例子，下面我们使用备忘录来解决斐波那契问题：

std::unordered_map<int, int> memo;

int Fibonacci(int n) {
  if (n == 0) {
		return 0;
	}
	if (n == 1 || n == 2) {
		return 1;
	}
  if (memo.count(n) > 0) {
    return memo[n];
  } else {
    memo[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
  }
	return memo[n];
}

现在，所有重复的节点都不存在了，我们只需要计算 Fibonacci(i) 一次。

使用制表

我们也可以使用制表来解决这个问题。要使用制表，我们可以定义一个数组或者一个向量来保存子问题的结果。

在 C++ 中，我们将使用 std::vector。

下面是使用制表实现的 Fibonacci 函数：

int Fibonacci(int n) {
  if (n == 0) {
		return 0;
	}
	if (n == 1 || n == 2) {
		return 1;
	}
  std::vector<int> d(n + 1);
  for (int i = 3; i <= n; i++) {
    d[i] = d[i - 1] + d[i - 2];
  }
  return d[n];
}

可选的其他改进

有一种叫 "状态压缩" 的改进方式。

状态压缩是动态规划中使用的一种技术，用于减少存储计算中间结果所需的内存量。 它涉及使用较小的数据结构（如位向量或哈希表）而不是数组或矩阵等较大的数据结构来表示子问题状态。 这有助于降低算法的空间复杂性，并有可能解决更大的问题或具有更复杂的子问题的问题。

针对当前情况，我们将 d 替换为 pre 和 curr 两个整数：

int Fibonacci(int n) {
  if (n == 0) {
		return 0;
	}
	if (n == 1 || n == 2) {
		return 1;
	}
  int pre = 1;
  int curr = 1;
  for (int i = 3; i <= n; i++) {
    int sum = pre + curr;
    pre = curr;
    curr = sum;
  }
  return curr;
}

框架

1. 找到所有的 base cases。

   在斐波那契问题中，所有的 base cases 包括 n == 0、 n == 1 以及 n == 2。

2. 找到所有的状态。

   在斐波那契问题中，所有的状态即是所有的非负数。

3. 找到状态转移方程。

   在斐波那契问题中，状态转移方程为 : dp[i] = dp[i - 1] + dp[i - 2]

提示

状态转换方程是一个数学方程，描述了系统状态如何随时间变化。 在动态规划的背景下，状态转换方程是一种方程，它描述了如何从最优解到其子问题构建问题的最优解。 通过使用状态转换方程，可以通过将其分解为较小的子问题，然后将最优解与这些子问题相结合，以找到较大问题的最优解来解决问题。

4. 找到所有的选择，并弄明白怎么去定义 DP 表。