动态规划进阶：复杂度优化与空间压缩

"动态规划2-张惜今" 在计算机科学和算法设计中，动态规划是一种强大的解决问题的方法，尤其适用于解决具有重叠子问题和最优子结构特征的问题。本资源由张惜今提供的动态规划入门讲解，主要关注如何优化动态规划的复杂度，以便解决更大规模的问题。 动态规划的核心在于通过构建状态转移方程来逐步求解问题。然而，当问题规模变得很大（如10^5或10^6）时，常规的动态规划算法可能会面临时间复杂度和空间复杂度的挑战。为了解决这个问题，我们可以从三个方面进行优化： 1. 减少状态数量：这通常涉及到重新定义状态，使得状态的数量减少。例如，在“灵梦的双重灵力”问题中，我们可以将状态表示为两个点的坐标和步数，而不是每一步的状态，这样可以显著降低空间复杂度。 2. 改变决策方式：优化决策过程，使其更高效。例如，在“蕾米的出门方案”问题中，我们可以通过调整状态表示，使得状态不仅包含当前时间点，还包含上一次出门的结束时间，从而避免了多次重复计算。 3. 优化决策效率：有时候，我们可以通过改变数据结构或算法来提高每次决策的执行速度。例如，使用滚动数组来避免不必要的状态维，对于只依赖于前一状态的问题，可以节省大量内存。 动态规划的时间复杂度计算通常遵循公式：时间复杂度 = 状态总数 × 决策数 × 每次决策的时间复杂度，而空间复杂度则包括状态总数和额外辅助空间。在实际应用中，如果空间有限（如32MB至256MB），即使空间要求不高，仍需考虑优化。 优化动态规划的空间复杂度，一种常见方法是使用滚动数组。比如在“灵梦的双重灵力”问题中，由于状态只依赖于前一个状态，可以使用滚动数组来存储状态，避免存储所有历史状态，从而减少空间需求。 在某些情况下，我们还可以通过改变问题的表示来优化。例如，在“蕾米的出门方案”问题中，通过将状态表示为当前时间和上次出门结束时间，我们可以更有效地计算办事方便值的总和，同时降低了状态维度，减少了计算量。 动态规划的优化是一个综合的过程，它涉及对问题的理解、状态的精炼、决策的优化以及数据结构的选择。通过巧妙地处理这些问题，我们可以让动态规划算法在处理大规模问题时依然保持高效。