题目重点：除最大点数外，返回对应策略的原始位置。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 按标准相邻不得同时取的训练合同，允许空选择，数值可为负。
- 平局跳过当前位置，只保证确定可行最优，不声称下标字典序最小。实际变体若要求至少取一项应改初始化。
解题路线
- best[i]为前i项最优，取当前=values[i−1]+best[i−2]，不取=best[i−1]。比较记录take[i]。
- 从i=n回溯：take则记录i−1并跳2，不取跳1。这个i代表尚待解释的前缀，不能用完整长度下的选择标志逐位拼接。
- 仅求数值可滚动两状态O(1)空间，但返回下标需要存决策或另算；不要把含回溯数组版本写成O(1)空间。
手动走一遍
[2,7,9,3,1]取[0,2,4]总12。[-2,-1]允许空时返回0和[]；若必须取一项则最优−1，合同不同。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def rob(values):
# Empty selection is permitted; ties skip the current position.
n=len(values);best=[0]*(n+1);take=[False]*(n+1)
for i in range(1,n+1):
candidate=values[i-1]+(best[i-2] if i>=2 else 0)
if candidate>best[i-1]:best[i]=candidate;take[i]=True
else:best[i]=best[i-1]
indices=[];i=n
while i>0:
if take[i]:indices.append(i-1);i-=2
else:i-=1
return best[n],indices[::-1]
复杂度
O(n)时间/O(n)决策与DP空间，返回k下标另O(k)。
易错点与追问
容易失分的边界
- 回溯取当前位置后只减1会生成相邻下标。
- 零/负分值时初始best为0意味着允许空，需公开。
继续深挖
- 环形首尾相邻时怎样拆两种首项合同？
- 要求所有最优策略时为何输出可能指数级？
