动态规划实例解析：火车转车费用与数字三角形最小路径

动态规划是一种在数学优化中使用的算法设计方法，用于解决具有重叠子问题和最优子结构的问题。在这个【标题】中，"动态转移方程"的核心概念是指在求解这类问题时，通过定义并维护一个表格或数组，用来存储每个子问题的解，从而避免重复计算，提高效率。动态规划通常涉及两个关键步骤：状态定义和状态转移方程。 例题2描述了一个实际生活中的旅行问题，即寻找从杭州到北京最低的火车费用路径。问题分为两类：一类是必须在杭州、上海、南京停靠后再继续旅程（采用贪心策略），子问题独立；另一类则是允许在这些城市之间转车，此时子问题可能存在相互依赖，不能简单地通过加总最小费用得到整体最优解。在这一例子中，动态规划通过构建二维数组f[I,j]来表示从当前节点到达终点的最小费用，使用递推公式f(i,j) = a[i,j] + min{f(i-1,j), f(i-1,j+1)}来计算。 对于给定的数字三角形问题，找到一条从第一层到最后一层权值之和最小或最大的路径，是经典的动态规划应用。这里通过自底向上的方式（从底层逐层递推）计算每一层节点到终点的最优解，利用状态转移方程f[i,j] = a[i,j] + min(f[i-1,j], f[i-1,j+1])来更新最优值。反之，也可以采用自顶向下的方式（递归过程），但效率较低，因为会存在大量重复计算。 在搜索算法中，特别是当问题规模较大时，如例1所示，时间复杂度会迅速增长。为优化性能，动态规划引入了剪枝策略，通过存储先前计算过的最优解（如在opt数组中），避免对已知结果进行重复计算。这种“记忆”功能是动态规划的核心优势，它显著降低了算法的时间复杂度，使之能够在大规模问题上求解。 总结来说，动态规划在处理此类问题时，通过定义状态、建立转移方程，以及运用剪枝技巧，有效地解决了具有重叠子问题和最优子结构的复杂问题。通过这两个实例，我们可以深入理解动态规划在实际问题中的应用和优化策略。