【算法 - 动态规划】从零开始学动态规划！（总纲）

动态规划

动态规划（Dynamic Programming，DP）是一种优化问题求解方法，通常用于解决具有 重叠子问题 和 最优子结构 性质的问题。它的基本思想是将原问题分解成更小的子问题，通过求解和保存这些子问题的解，避免重复计算，从而提高算法的效率。

基本概念：

1. 最优子结构：

   • 最优子结构是指问题的最优解可以通过 子问题的最优解递归 构建而成。在动态规划中，原问题被分解为更小的子问题，每个子问题都有自己的最优解。通过合并这些最优解，我们可以得到整体问题的最优解。

2. 重叠子问题：

   • 动态规划问题会涉及到重叠子问题，即在解问题的过程中会多次遇到 相同的子问题。为了避免重复计算，动态规划使用记忆化或者其他方法来保存子问题的解。

3. 状态转移方程：

   • 状态转移方程是问题建模的关键，它描述了问题的 当前状态 和如何从之前的状态 转移到新状态。通过定义合适的状态和状态之间的 转移关系，可以得到问题的递推解法，将子问题和整体连接了起来。

4. 存储中间结果：

   • 为了避免重复计算，动态规划通常使用数组、矩阵或字典等数据结构来 存储中间结果。这些中间结果包括子问题的解，可以在需要时 直接获取，而不必重新计算。

5. 自底向上或自顶向下的求解方法：

   • 动态规划可以采用 自底向上（Bottom Up）或自顶向下（Top Down）的求解方法。自底向上是从最小的子问题开始逐步求解，而自顶向下是通过递归从原始问题开始，逐步分解为子问题。

这几个基本概念通常共同作用，构成了动态规划算法的基础。具体步骤包括：

定义状态： 确定问题的状态，即问题的子结构和需要求解的变量。

找到状态转移方程： 建立子问题之间的递推关系，通过状态之间的转移来描述问题的求解过程。

初始化边界条件： 将最小的子问题的解设置为初始条件，为递推提供基础。

自底向上或自顶向下求解： 使用 迭代（自底向上）或 递归（自顶向下）的方法，按照状态转移方程求解子问题，最终得到整体问题的解。

适用场景

动态规划广泛应用于解决各种问题，例如 最短路径问题、背包问题、编辑距离 等。通过合理建模问题，定义好 状态 和 状态转移方程 ，就能够高效地解决复杂的优化问题。

---

看完以上内容，是不是在遇到一道 动态规划 的题目仍然不知道如何思考，从哪开始着手写？

答案是：从递归开始！

暴力递归

1. 基本思想：

   • 是一种很朴素的解决问题的方法，通过递归考察所有可能的解决方案来找到办法。有明确的不需要继续递归的条件，即 base case。

2. 重复计算问题：

   • 暴力递归通常不会对重复的子问题进行记忆，可能会导致相同子问题 重复计算。

3. 时间复杂度问题：

   • 由于暴力递归会考虑所有可能的组合，可能会导致指数级的时间复杂度。

4. 适用情况：

   • 当问题规模较小且可能的解决方案数量有限时，暴力递归可能表现的很有效。

要想写出递归函数，要明确以下几点：

1. 定义 Base Case :

• 递归函数应该有一个或多个基本情况，即不再递归调用的情况。
• 基本情况通常是问题可以直接解决的最小子问题。

2. 定义状态

• 状态是问题的变量，用于描述问题的不同方面，应该包含问题的所有相关信息。

3. 定义递归函数的功能

• 只有明确了递归函数的功能，才能知道需要哪些状态变量。
• 同时也明确了主函数调用时，如何传递初始参数。

---

因此，要想写出动态规划，大体步骤就是：

1. 思考题目如何用最最普通的思路写出递归函数

2. 画图，寻找哪些地方会存在可以优化的点

3. 保存部分或全部状态，避免重复计算

接下来的 系列文章 会带大家一步一步的从 暴力递归 优化出 动态规划 ，并深入理解动态规划的基本概念以及书写步骤！

敬请期待一下吧 ~