解题思路
题意可抽象为:共有 T 次迭代(编号 0∼T−1)。当跳过第 t+1 步(0≤t<T−1)时,相当于复用第 t 步的计算结果,会产生损失值 loss[t]。因此一共有 T−1 个“可跳过的位置”(对应步骤 1∼T−1),每个位置选中则付出相应损失。
要求:恰好跳过 k 步,且不能连续跳过两步(即所选位置不能相邻),使总损失最小;若无解输出 −1。
这是典型的“带相邻限制的选取最小代价”问题,使用动态规划(DP):
- 设 n=T−1,位置 i=1∼n 对应损失代价 ci=loss[i−1]。