题目重点：按明确起终点计算访问成本，区别于可以从第1阶开始并跳出数组的标准楼梯版本。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练必须访问下标0和n−1，每访问一个格子支付该格cost；空数组约定0，单格支付自身。
- 只向前走1/2步，允许负cost；没有回边，不产生负环。
- 若正式允许从1开始或终点在数组外，需要更换初值/答案，不能只改函数名字。
解题路线
- dp[i]表示必须落在i时的最小累计成本，dp[0]=cost[0]，dp[1]=cost[0]+cost[1]。这两个初值来自强制起点，不是“从0或1任选”的楼梯模板。
- i≥2时最后一步只能从i−1或i−2到来，因此dp[i]=cost[i]+min(dp[i−1],dp[i−2])。所有合法路径均由两类前驱覆盖，没有遗漏。
- 正确性：任意到i的最优路径若前缀不是其前驱最优路径，可替换前缀得到更低成本，矛盾；所以选两个最优前驱中的较小值并支付当前cost即可。
- 只保留最近两项，循环时同时更新避免覆盖旧dp[i−2]；按下标访问输入，不能创建cost[2:]切片后仍声称额外空间O(1)。
- 负cost也不影响DAG最短路递推，跳过一个负cost节点可能变差，不能用每步贪心选最低下一格。强制最后一格时答案dp[n−1]，不是最后两项min。
- 要返回路径，另保存前驱，遇并列定义偏好1步或2步。若只返回值，保留整个dp表没有必要。
- 扩展允许跳集合J时对所有合法前驱取min，O(n|J|)；超长跳、禁止落点或取模计数各是新问题，不应套当前两个状态而不重新核转移。
手动走一遍
[5,100,1]必须从0到2，可一步跨度2，总6。[5,−10,1]逐格走总−4，比跳过负成本的6更小。[10,15]本合同支付25；可任选起点的楼梯版可能给10或15，说明初值必须澄清。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Start at index 0, finish at n-1, take 1/2 steps and pay every visited cost.
Costs may be negative; empty input returns zero by training convention.
"""
def minimum_path_cost(costs):
if not costs:
return 0
if len(costs) == 1:
return costs[0]
previous_two = costs[0]
previous_one = costs[0] + costs[1]
for i in range(2, len(costs)):
previous_two, previous_one = previous_one, costs[i] + min(previous_two, previous_one)
return previous_one
复杂度
O(n)时间、O(1)额外空间，只返回值；返回路径需要O(n)前驱/输出。大整数加比较按数值位数另计。
易错点与追问
容易失分的边界
- 套楼梯初值允许从1开始。
- 答案取min最后两项而不是强制终点。
- 负cost用局部贪心。
- 切片复制却声称常量工作空间。
继续深挖
- 终点在数组外如何修改？
- 怎样重建最优路径？
- 跳跃上限K怎样优化？
- 若某些格子禁止落点怎么表达不可达？
