动态规划
动态规划（Dynamic Programming，简称DP）是一种常用于解决优化问题的算法思想，它通常用于解决具有重叠子问题和最优子结构性质的问题。动态规划通过将问题分解成小的子问题，并在解决这些子问题的基础上构建问题的最优解。以下是动态规划的基本概念和步骤：
- 确定状态：首先要确定问题的状态，这些状态可以表示问题的各个子情况。状态的选择往往取决于问题的特性，通常用一个或多个变量表示状态。
- 定义状态转移方程：状态转移方程描述了状态之间的关系，它告诉我们如何从一个状态转移到另一个状态。这个方程通常以递归的方式定义，并用数学形式表示。状态转移方程是动态规划问题的核心。
- 初始化：确定初始状态的值，即最小子问题的解或者初始条件。
- 自底向上或自顶向下求解：动态规划可以采用两种方式求解，自底向上和自顶向下。自底向上从最小子问题开始，逐步求解更大规模的问题，直到达到原始问题。自顶向下从原始问题开始，逐步分解成子问题，直到达到最小子问题。通常，自底向上的方法更具效率，因为它避免了重复计算子问题。
- 记忆化存储（可选）：为了避免重复计算子问题，可以使用一个数据结构来存储已经计算过的结果，以便以后直接获取。这通常称为记忆化存储或缓存。
动态规划通常用于解决一些经典问题，如背包问题、最长公共子序列问题、最短路径问题等。它的核心思想是通过将问题分解成子问题并保存子问题的解来降低问题的复杂度，从而有效地解决复杂的优化问题。