动态规划解题策略：走第i步的四种选择分析

"走第i步时有四种方案-noip动态规划(夏令营讲稿)" 本文主要围绕动态规划这一主题展开，特别关注了一个具体的问题——在每一步有四种行动方案的情况下的决策优化。动态规划是一种解决多阶段决策问题的策略，通过逐步构建最优解，以达到在特定约束下最大化或最小化某个目标。 首先，讲解了动态规划的基本概念。它是一种最优化的思想，用于处理具有阶段性的决策问题，其中每个阶段的决策会影响后续阶段的状态。在不断变化的状态中，动态规划的目标是找到一个决策序列，使得在满足某些条件的情况下达到最优。 接着，文章引入了一个具体的例子，即从点P到点A寻找最短路径的问题。这个问题展示了动态规划的递归特性，即求解当前问题需要依赖于子问题的解。通过递归公式，我们可以看到求解P(A)的最短路径需要先知道P(B)和P(C)的最短路径，进而依次回溯，直至求得所有阶段的最短路径。 在实际应用动态规划解决问题时，通常会用到二维或更高维度的数组来存储中间状态。例如，在解决上述路径问题时，可能会使用两个数组h和v分别存储东西方向和南北方向的道路长度。这种数据结构使得我们能够有效地进行状态转移，计算每个阶段的最优解。 在题目描述中，提到了一个具体的状态转移方程`f[i,j,k]=max{ f[i-1,j,k], f[i-1,j-1,k]∣j-1<>k, f[i-1,j,k-1] ∣j<>k-1, f[i-1,j-1,k-1]}+a[j,y1]+a[k,y2]`。这个方程描述了一个三重循环的动态规划问题，其中`f[i,j,k]`表示到达位置`(i, j)`且有两条路径分别到达`(y1, y2)`的最短距离。四个情况分别对应了四种可能的路径选择：两条路径都向右，第一条路径向下第二条路径向右，第二条路径向下第一条路径向右，以及两条路径都向下。通过这些情况，我们可以计算出每个位置的最优值，并最终得到整个问题的解，即`f[m+n-2,m,m-1]`。 动态规划是一种强大的算法思想，它在处理复杂问题时能够有效地避免重复计算，通过构建状态空间并利用递推关系找到全局最优解。在这个特定的例子中，我们看到了如何将这种思想应用于解决具有多种选择的路径问题，通过状态转移方程和适当的数据结构来求解最短路径。