介绍

**动态规划（Dynamic Programming, DP）**是一种用于解决复杂问题的算法思想。它将一个复杂问题分解成更小的子问题，通过保存子问题的结果，避免重复计算，从而提高算法的效率。动态规划特别适用于具有重叠子问题和最优子结构性质的问题。

动态规划的两个关键性质：

• 重叠子问题（Overlapping Subproblems）:问题可以被分解成相同的子问题，这些子问题在求解过程中会被多次用到。通过保存子问题的解，可以避免重复计算。例如，斐波那契数列的计算中，fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)，其中 fibonacci(n-1) 和 fibonacci(n-2) 会被多次计算。
• 最优子结构（Optimal Substructure）:一个问题的最优解包含其子问题的最优解。这意味着可以通过解决子问题的最优解来构造原问题的最优解。例如，求解最短路径问题时，子路径的最优解可以帮助找到整体路径的最优解。