选择利润后跳过指定位置：逆序DP与负数合同

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• a[i]为非负整数，同时表示利润与跳过数；越过末尾即结束。
• 初始在0，每位置最多访问一次；负数回跳是另一个模型，不能沿用本DP。

解题路线

1. 每状态只有skip和take两条边，目标位置均>i，因此是DAG。逆序保证两种后继答案已知。
2. dp[i]=max(dp[i+1],a[i]+dp[min(n,i+1+a[i])])，边界dp[n]=0。所有后续选择只依赖下个位置，满足最优子结构。
3. 负数允许向回走时可能成环；还要确认利润是否可重复领取、何时停止。有环时不能简单改索引再递归，正收益循环甚至导致无界答案。

手动走一遍

[2,1,4,1]：选0得2后到3再得1，总3；跳0选1得1后到3得1，总2；跳到2选4得4，最优4。[0,0]虽利润零也只跳一步，不会自环。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def max_profit(a):
    if any(type(x) is not int or x < 0 for x in a):
        raise ValueError("nonnegative integer rewards required")
    n = len(a)
    dp = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        dp[i] = max(dp[i + 1], a[i] + dp[min(n, i + 1 + a[i])])
    return dp[0]

复杂度

O(n)时间、O(n)空间；重建方案再记录每个状态的决策。跳跨度任意，不能只保留固定两格状态。

易错点与追问

容易失分的边界

• 跳目标是i+1+a[i]，不是i+a[i]。
• 本题与HouseRobber固定间隔不同，不能直接套其O(1)两状态。

继续深挖

• 利润profit[i]和跳数skip[i]独立时公式怎样推广？
• 如果必须选至少一次，怎么避免空方案0覆盖全负利润？