求最优路径算法：带阶段方向成本的槽位全遍历问题

是否存在类似问题 #

存在。这类问题属于区间动态规划的典型场景，是旅行商问题（TSP）的优化变种，核心通过区间状态扩展避免暴力枚举所有路径的高复杂度。LeetCode、Codeforces上有不少同类型的区间DP题目，比如需要覆盖连续区间并计算最小成本的路径规划问题。

问题分析 #

你的问题本质是：从起点s出发遍历所有n个槽位，共进行n-1次移动；第i次移动时，左移（非最左）或右移（非最右）的成本固定，与移动距离无关。目标是求最小总成本及对应路径。

关键观察：由于移动成本只和移动次数、方向有关，每次移动的本质都是将已访问的区间向左或向右扩展一个槽位。比如当前已访问槽位是区间[l, r]，下一次移动只能扩展到[l-1, r]（左移一次）或[l, r+1]（右移一次），因此可以用区间DP建模。

动态规划解法 #

状态定义 #

定义dp[l][r][0]表示已访问槽位区间[l, r]，且当前位于左端点l时的最小总成本；dp[l][r][1]表示已访问区间[l, r]，当前位于右端点r时的最小总成本。

初始状态 #

起点s对应的初始区间是[s, s]，此时未进行任何移动，成本为0：

dp[s][s][0] = dp[s][s][1] = 0

其他所有状态初始化为无穷大（表示不可达）。

状态转移方程 #

对于区间[l, r]，已访问槽位数量为cnt = r - l + 1，意味着已经完成cnt - 1次移动，下一次移动是第cnt次（第1次移动后cnt=2，第2次移动后cnt=3，以此类推）。

• 若当前在左端点l，状态只能由[l+1, r]区间转移而来：

  dp[l][r][0] = min(
      dp[l+1][r][0] + left_cost[cnt],  // 从l+1左移到l，使用第cnt次左移成本
      dp[l+1][r][1] + left_cost[cnt]   // 从r左移到l，成本相同
  )
  

• 若当前在右端点r，状态只能由[l, r-1]区间转移而来：

  dp[l][r][1] = min(
      dp[l][r-1][0] + right_cost[cnt],  // 从l右移到r，使用第cnt次右移成本
      dp[l][r-1][1] + right_cost[cnt]   // 从r-1右移到r，成本相同
  )
  

其中left_cost[i]是第i次移动的左移成本，right_cost[i]是第i次移动的右移成本（数组下标从1开始对应第1次移动）。

计算顺序 #

按区间长度从小到大扩展计算：

• 先处理长度为1的区间（初始状态）；
• 再处理长度为2到n的区间；
• 最终计算覆盖所有槽位的区间[1, n]。

路径记录 #

维护回溯数组prev[l][r][0/1]，记录每个状态的前驱来源：

• prev[l][r][0] = 0表示从dp[l+1][r][0]转移而来，prev[l][r][0] = 1表示从dp[l+1][r][1]转移而来；
• prev[l][r][1] = 0表示从dp[l][r-1][0]转移而来，prev[l][r][1] = 1表示从dp[l][r-1][1]转移而来。

从最终状态min(dp[1][n][0], dp[1][n][1])对应的位置（1或n）开始回溯，记录经过的槽位，最后反转回溯结果得到正向最优路径。

复杂度分析 #

• 时间复杂度：O(n²)，遍历所有O(n²)个区间状态，每个状态转移计算为O(1)；
• 空间复杂度：O(n²)，用于存储DP数组和回溯数组。

相比暴力O(n!)解法，效率提升几个数量级，可处理n=1e3甚至更大规模的输入。

内容的提问来源于stack exchange，提问作者Casper Kejser