概述
动态规划：解决复杂问题的简单方法
动态规划（Dynamic Programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的，通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。
什么是动态规划？
动态规划是一种算法设计技术，它将复杂问题分解成更小的子问题，并存储这些子问题的解，以避免重复计算。这种技术通常用于求解最优化问题，例如背包问题、最长公共子序列、最短路径问题等。
动态规划的核心思想
动态规划的核心思想是“记住你曾经解决过的子问题”。这意味着，当我们解决一个问题时，我们会将解决方案存储起来，这样当我们再次遇到相同的子问题时，我们可以直接使用已存储的解决方案，而不是重新计算。
动态规划的步骤
- 定义子问题：将原问题分解为更小的子问题。
- 实现递推关系：找出子问题之间的关系，以便一个子问题的解可以用来解决另一个子问题。
- 初始化边界条件：确定一些基础情况的解。
- 计算顺序：确定子问题的计算顺序，以确保在解决一个子问题时，它所依赖的子问题已经被解决。
- 构建解决方案：使用子问题的解来构建原问题的解。
动态规划的例子
让我们以经典的斐波那契数列为例。斐波那契数列的定义是：F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)。
使用动态规划，我们可以这样计算斐波那契数列：
def fibonacci(n):
# 初始化边界条件
if n == 0:
return 0
if n == 1:
return 1
# 创建一个数组来存储子问题的解
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
# 计算子问题的解，并存储在dp数组中
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
# 返回原问题的解
return dp[n]
动态规划的优势
- 避免重复计算：通过存储子问题的解，动态规划可以避免重复计算，从而提高效率。
- 分治策略：动态规划将问题分解为更小的子问题，这使得问题更容易解决。
- 适用于各种问题：动态规划可以应用于各种类型的问题，包括背包问题、最长公共子序列、最短路径问题等。
动态规划总结
动态规划是一种强大的算法设计技术，它通过将复杂问题分解为更小的子问题并存储这些子问题的解来提高效率。掌握动态规划不仅可以提高你的编程技能，还可以帮助你解决各种实际问题。
优化技巧：滚动数组
滚动数组是一种在动态规划（DP）问题中优化空间复杂度的技巧。它通过“滚动”或覆盖旧的数据来重用数组空间，从而减少所需的内存。
原理
在动态规划中，我们通常使用二维数组来存储中间结果。例如，如果我们要解决一个有 n 个阶段的问题，每个阶段有 m 种选择，我们可能需要一个 n x m 的二维数组 dp。
dp[i][j]存储的是在第i阶段选择j时的最优解。
在某些情况下，我们发现在计算dp数组的过程中，当前阶段的结果只依赖于前一阶段的结果。这意味着我们不需要存储所有阶段的结果，只需要保留最近两个阶段的信息就足够了。
实现步骤
- 初始化: 创建一个二维数组
dp，但只使用两行（或两列，取决于问题的性质）。 - 计算: 在计算过程中，交替使用这两行（或两列）来存储当前阶段和前一阶段的结果。
- 更新: 在每个阶段结束时，更新行（或列）的引用，以便下一阶段可以使用正确的数据。
优点
- 减少空间复杂度: 对于某些问题，滚动数组可以将空间复杂度从
O(n * m)降低到O(m)或O(n)。
缺点
- 代码复杂性增加: 使用滚动数组会使代码更难以理解和维护，因为它涉及到对数组索引的仔细管理。
示例
假设我们有一个 n x m 的 dp 数组，我们只使用两行来存储数据。在计算 dp[i][j] 时，我们实际上会交替使用 dp[i % 2][j] 和 dp[(i - 1) % 2][j]。
滚动数组总结
滚动数组是一种在满足特定条件时非常有用的空间优化技巧。它通过减少所需的内存来提高程序的性能，但同时也增加了代码的复杂性。在决定是否使用滚动数组时，需要权衡空间优化和代码可读性。