动态规划入门：灵梦的灵符修复

"动态规划1-张惜今" 动态规划是一种优化技术，主要应用于解决具有重叠子问题和最优子结构的复杂问题。它的核心思想是通过将原问题分解为更小的子问题，并存储子问题的解，避免重复计算，从而提高效率。这种解决问题的方法在计算机科学和运筹学中有着广泛的应用，尤其是在算法设计中。 在这个例子中，问题被设定为一个与博丽灵梦修复结界的灵符游戏。灵符是一个三角形结构，由数字组成，代表不同位置的修复值。灵梦需要从顶部开始，按照左下或右下方向移动，直到达到底部，目标是找到一条路径，使得路径上的数字之和最大。 首先，最容易想到的解决方案是穷举所有可能的路径，对每条路径计算其总和并比较，选取最大的那个。然而，这种方法的时间复杂度极高，因为它涉及到指数级别的计算，例如对于n=4的情况，需要计算2^(4-1)=8条路径，总共24次计算。随着n的增加，计算量将以指数速度增长，对于大一点的n（如n=100或1000），这种方法显然是不可行的。 动态规划的解决方案则更加高效。它采用自底向上的策略，通过记录每个位置到该位置为止的最大修复值，避免了重复计算。对于灵符问题，我们可以从最后一层开始，逐层向上计算每个位置的最大修复值。每层中的每个点只需要与它的左下和右下的点进行一次比较和一次加法操作，然后选择较大值作为当前点的最大修复值。这样，对于n层的灵符，总共需要进行(1+4)*4/2-1=9次计算，即18次，相比于穷举方法，大大减少了计算量。 总结动态规划的关键特性： 1. 最优子结构：问题的最优解可以通过子问题的最优解来构造。 2. 重叠子问题：在寻找最优解的过程中，许多子问题会被重复计算。 3. 状态与决策：在每个阶段，动态规划通过做出决策（如选择路径）来定义状态。 4. 记忆化：通过存储子问题的解来避免重复计算，这通常通过使用数组或表格实现。 动态规划不仅限于解决路径规划问题，它还可以应用于背包问题、最长公共子序列、矩阵链乘法等多种问题。然而，应用动态规划时需要注意，问题必须能够划分为离散的阶段，且满足上述最优子结构和重叠子问题的特性。此外，不是所有问题都适合使用动态规划，需要根据问题的具体情况选择合适的方法。