动态规划：数塔问题与公路广告牌收益最大化

动态规划是一种在解决具有重叠子问题和最优子结构的最优化问题时所采用的高效算法策略。它强调通过分阶段决策，逐步求解问题，而不是直接寻找全局最优解。在这个过程中，每个阶段的决策都会影响后续阶段，形成一个决策序列，体现了动态变化的特性。 在给定的"存储、求解-动态规划讲义"中，以数塔问题为例来讲解动态规划的应用。数塔问题描述了一个从顶层开始，每一步可以选择向左或向右移动，目标是在给定路径上选择数值，使得路径总和最大。原始信息包括数塔的层数（存储在整型变量n中）和每层的数值（用二维数组data表示的下三角矩阵形式）。 动态规划方法的关键在于将原问题分解为多个子问题，并利用子问题的解来构建原问题的解。在数塔问题中，首先通过阶段划分，比如针对第五层的决策，我们看到有四种可能的选择，每一种选择都将导致数塔转化为一个较小规模的子问题。例如，选择19对2的路径将使得第四层的问题变成只考虑19；选择10对18和9的路径则分别处理这两个分支。 在算法设计阶段，动态规划的过程是递归的，通过已知子问题的最优解来计算当前问题的最优解。例如，第五层的决策导致第四层和第五层的和分别为21（2+19）和28（18+10）。这个递推过程会持续到数塔的最底层，每一次决策都是为了寻找全局最优解，而非局部最优。 与贪婪算法不同，贪婪算法通常采取每次选择当前状态下看起来最好的解决方案，但不一定会得到全局最优解。数塔问题中，贪婪策略的两种路径选择都没有找到最大和，而动态规划则通过多阶段决策，逐步优化问题，最终找到全局最优解——9+12+10+18+10=59。 总结来说，动态规划的核心在于其通过分解问题、存储中间结果并利用这些结果来优化决策，从而避免重复计算，提高了求解复杂问题的效率。在实际应用中，动态规划广泛用于诸如背包问题、最长公共子序列、最短路径等具有相似结构的问题。理解动态规划的本质和应用，能够帮助我们在面对这类问题时找到更高效的解决方案。