03.动态规划1

动态规划是一种解决问题的方法，特别适用于解决那些具有重叠子问题和最优子结构的复杂问题。在动态规划中，我们不是通过递归的方式反复求解相同的子问题，而是将子问题的解存储起来，避免了重复计算，从而提高了算法的效率。 1. **动态规划概述** 动态规划的核心思想是将复杂的问题分解成一系列较小的子问题，对每个子问题只求解一次，然后用这些子问题的解来构建原问题的解。它通过构建一个表格（通常是二维数组）来保存子问题的解，以便后续使用。这种方法降低了时间复杂度，因为不需要多次计算相同的子问题。 2. **解题步骤** 解决动态规划问题通常分为以下几步： - 定义状态：确定问题的状态是什么，通常是一个或多个变量的组合。 - 定义决策：在每个状态下，我们可以做出哪些决策。 - 定义状态转移方程：根据决策，从一个状态转移到另一个状态的规则。 - 初始化：设定基础状态的解，通常是问题的边界条件。 - 构建解：按照状态转移方程从基础状态开始，逐步计算出所有状态的解。 3. **示例问题** - **斐波那契数列**：斐波那契数列是一个经典的动态规划问题，可以通过定义状态`F[i]`表示第`i`个斐波那契数，然后根据`F[i] = F[i-1] + F[i-2]`来计算。在给定的例子中，动态规划的实现比递归实现更高效，因为它避免了重复计算。 - **找零问题**：给定一组不同面值的硬币和一个找零金额，求最少需要多少枚硬币。在这个问题中，状态`F[i]`表示用这些硬币找零`i`的最小硬币数量。动态规划通过比较加上一枚硬币和不加硬币的两种情况，选取更优解。 - **背包问题**：基本的背包问题是决定在容量限制下，如何选取物品以达到最大价值。状态`value[i][j]`表示前`i`件物品装入容量为`j`的背包所能获得的最大价值。通过遍历所有可能的物品选择情况，我们可以构建出状态转移方程。 4. **动态规划的特性** - **最优子结构**：问题的最优解可以通过其子问题的最优解构造出来。 - **无后效性**：当前状态的决策不会影响之前状态的决策，即一旦做出某个决策，就不需要回顾过去，只关注当前和未来的决策。 5. **效率比较** 动态规划相对于递归的重要优势在于避免了重复计算。在上述的找零问题中，动态规划实现`CoinRow1`通过存储子问题的解避免了重复计算，而递归实现`CoinRow2`则会重复计算相同的子问题，导致效率降低。 6. **注意事项** 理解动态规划时，要注意问题的自下而上的求解过程，而不是简单地根据递推关系。例如，在背包问题中，包括第`i`件物品和不包括第`i`件物品的组合是不同的，不能仅凭直觉认为包括第`i`件物品的组合一定更好，而应综合考虑所有可能性。 动态规划是一种强大的工具，用于解决优化问题，尤其是在面临重叠子问题时。通过正确理解和应用动态规划，可以有效地设计出高效的算法，解决复杂问题。