动态规划入门：最优子结构与灵梦的灵符问题

"该资源是一份关于动态规划的讲解，由张惜今主讲，主要介绍了动态规划的基本概念和应用，通过一个关于博丽灵梦修复灵符的问题来阐述动态规划的思想，即如何通过最优子结构减少重复计算，提高效率。" 在动态规划中，最优子结构是一个核心概念。它意味着当前状态的最优解能够决定后续状态的最优解。如果一个问题的最优解包含其子问题的最优解，那么这个问题就具有最优子结构。在这个例子中，灵梦修复灵符的问题中，每一步选择最大修复值的路径，就是利用了最优子结构。在计算过程中，我们不再需要重复计算已经走过的位置，而是直接引用之前计算得到的最优值。 最容易想到的解决方案是对所有可能的路径进行枚举，但是这种方法的时间复杂度非常高，随着问题规模的增加，计算量呈指数级增长。例如，当n=4时，需要计算2^(4-1)=8条路线，总共24次计算。如果n更大，如n=100或n=1000，计算量将急剧增加。 动态规划的策略是避免这种重复计算，通过记录每一步的最大修复值来优化。每层作为一个独立的问题，我们只需要计算到达当前位置的最大修复值，然后将这个值传递给下一层。对于n=4的情况，采用动态规划后只需计算18次，明显减少了计算量，而且随着n的增长，动态规划的效率优势更加显著。 动态规划定义为一种运筹学分支，用于解决多阶段决策过程的最优化问题。它将复杂问题分解为一系列更小的单阶段问题，并确保这些阶段满足最优子结构，即局部最优解能导出全局最优解。这种方法的效率较高，因为它减少了冗余计算，但同时也有一定的局限性，如问题必须能够划分为阶段且满足特定条件。 总结来说，动态规划是一种通过最优子结构来避免重复计算、提高效率的解决问题的策略。在灵梦修复灵符的问题中，通过存储和重用已知的最优解，我们能够有效地找到全局最优解，而不必遍历所有可能的路径。这种思想在很多实际问题中都有广泛应用，如背包问题、最长公共子序列等。