什么样的问题应该使用动态规划？

你是否有这样的困惑？在掌握了一些基础算法和数据结构之后，碰到一些较为复杂的问题还是无从下手，面试时自然也是胆战心惊。究其原因，可以归因于以下两点：

• 对动态规划相关问题的套路和思想还没有完全掌握；
• 没有系统地总结过究竟有哪些问题可以用动态规划解决。

知己知彼，想要把动态规划作为你的面试武器之一，就得足够了解它；而应对面试，总结、归类问题其实是个不错的选择，这在我们刷题的时候其实也能感觉得到。

动态规划问题的典型特点

相信你已经了解了动态规划的基本概念，如何快速判断一个问题是否能使用动态规划来解决，可以结合动态规划问题的主要典型特点判断：

• 最优子结构
• 重叠子问题
• 无后效性
• 状态转移方程

如果当遇到一个问题具备这些特点时，基本上可以确定可以使用动态规划来解题。使用动态规划可以帮助避免重复计算，提高算法的效率。比如，最短路径问题、最小生成树问题、最长递增子序列问题（LIS）、最优二叉树问题、背包问题等等。

1、最优子结构

最优子结构是指一个问题的最优解可以通过其子问题的最优解来构造。这意味着问题可以被分解为更小的子问题，而这些子问题的最优解能够构成原问题的最优解。

以下通过几个案例说明最优子结构的概念：

1. 最短路径问题（Dijkstra算法）：

案例说明： 在图的最短路径问题中，如果从节点A到节点C的最短路径包含了从A到B的最短路径，那么问题具有最优子结构。因为问题的最优解可以通过子问题的最优解来构造。即可以通过将A到B的最短路径连接到B到C的最短路径来构造整体的最短路径。

1. 最长递增子序列问题：

案例说明： 在最长递增子序列问题中，考虑一个序列，其中的最长递增子序列以某个元素结尾。如果去掉最后一个元素，得到的序列仍然是之前序列的最长递增子序列，那么整体的最长递增子序列可以通过子序列的最优解来构造。即该问题具有最优子结构。

1. 动态规划背包问题（0/1背包问题）：

案例说明： 在0/1背包问题中，对于每个物品，我们可以选择将其放入背包或者不放。如果选择放入背包的方案是最优的，那么问题具有最优子结构。

2、重叠子问题

重叠子问题是指在问题的解决过程中，同样的子问题被多次计算。以下通过几个案例说明重叠子问题的概念：

1. 斐波那契数列：
   • 问题描述： 斐波那契数列是一个典型的具有重叠子问题的问题，其中每个数是前两个数之和，即 F(n)=F(n−1)+F(n−2)。
   • 重叠子问题： 在计算 F(n) 时，很可能会重复计算相同的子问题，例如 F(n−1) 和 F(n−2)。
   • 解决方法： 使用记忆化存储中间结果，将已经计算过的 F(n−1) 和 F(n−2) 存储起来，避免重复计算。
2. 动态规划背包问题（0/1背包问题）：
   • 问题描述： 0/1背包问题是一个典型的动态规划问题，其中需要在给定容量的情况下选择物品，使得总价值最大。
   • 重叠子问题： 在计算每个子问题时，很可能会多次计算相同容量和相同选择下的最优解。
   • 解决方法： 使用记忆化存储中间结果，将已经计算过的子问题的最优解存储起来，避免对相同子问题的重复计算。
3. 最长公共子序列问题：
   • 问题描述： 给定两个序列，找到它们的最长公共子序列的长度。
   • 重叠子问题： 在计算两个序列的最长公共子序列时，很可能会多次计算相同位置的子序列的长度。
   • 解决方法： 使用动态规划时，可以通过存储已计算的子序列长度来避免对相同子序列的重复计算。

这些例子中，重叠子问题表现为在问题的解决过程中，同样的子问题被多次计算。动态规划通过存储中间结果，避免了对这些重叠子问题（相同子问题）的重复计算，提高了算法的效率。

3、无后效性

无后效性是指一个阶段的状态一旦确定，就不受后续阶段的影响。这意味着可以通过局部最优解构建全局最优解。

1. 最短路径问题（Dijkstra算法）：
   • 无后效性： 在求解最短路径时，从起点到某个节点的最短路径是局部最优解。这个最短路径的计算不受之后路径的选择影响，只取决于当前节点的状态。
   • 例子： 考虑从图中的节点A到节点C的最短路径。如果这条路径包含了从A到B的最短路径，那么问题具有无后效性。因为A到B的最短路径已经确定，不受之后路径的选择影响。
2. 动态规划背包问题（0/1背包问题）：
   • 无后效性： 在0/1背包问题中，选择是否将某个物品放入背包是一个局部的决策。这个决策不会影响后续物品的选择，只与当前物品的状态和背包的状态有关。
   • 例子： 对于每个物品，我们只关心是否放入背包，而不考虑这个决策对后续物品的影响。这是因为每个物品的选择都是相互独立的，无后效性使得我们可以局部地考虑每个物品。
3. 最长递增子序列问题：
   • 无后效性： 在求解最长递增子序列时，对于每个元素，我们只关心其前面比它小的元素，而不考虑它后面的元素。
   • 例子： 考虑一个序列，其中的最长递增子序列以某个元素结尾。如果去掉最后一个元素，得到的序列仍然是之前序列的最长递增子序列，那么整体的最长递增子序列可以通过子序列的最优解来构造。

在动态规划中，无后效性的概念表明问题的某个阶段的最优解不依赖于后续阶段的状态，只依赖于当前阶段的状态。这使得我们在求解问题时可以局部地考虑每个阶段，而不必担心全局的状态变化。

4、状态转移方程

状态转移方程是动态规划问题中 定义问题状态 及 状态之间关系 的方程。它描述了问题的递推关系，表达了如何从一个状态转移到另一个状态，从而通过逐步求解子问题来解决整个问题。

1. 斐波那契数列：
   • 状态定义： 令 F(n) 表示第n 个斐波那契数。
   • 状态转移方程：F(n)=F(n−1)+F(n−2)，其中 F(0)=0，F(1)=1。
   • 解释： 斐波那契数列的状态转移方程表示当前斐波那契数等于前两个斐波那契数之和。这个递推关系定义了问题的状态和状态之间的转移规则。
2. 最长递增子序列问题：
   • 状态定义： 令 dpi 表示以第 i 个元素结尾的最长递增子序列的长度。
   • 状态转移方程：dpi = max(dpj + 1)，其中 0 ≤ j <i 且 numsj < numsi。
   • 解释： 最长递增子序列问题的状态转移方程表示以第 i 个元素结尾的最长递增子序列长度等于前面比它小的元素的最长递增子序列长度加1。

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！