Uber OA 跳跃最大得分：尾数 3 的质数与整数变体

题意与假设

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

• 从数组下标 0 出发，每次向右跳 1 步，或跳一个允许的正整数步长；经过的落脚格分数相加，必须落在最后一格。
• prime_only=true 时允许个位为 3 且为质数的步长；false 时允许所有个位为 3 的正整数。33 在后者合法、在前者非法，两个题目口径不能无提示合并。
• 分数可正可负；起点格分数计入总和。题目未说明起点是否计分，若现场定义不同，只需把 dp[0] 改为 0。

解题路线

1. 先根据数组长度枚举小于 n 的合法特殊步长；质数版可先筛出质数，再按个位筛选。无论哪版都加入步长 1。
2. 设 dp[i] 为精确落在 i 时的最大路径分数。转移 dp[i]=values[i]+max(dp[i−step])，其中 step≤i 且合法。
3. 所有跳跃只向右，状态依赖更小下标，按 i 递增计算即可；最后返回 dp[n−1]。步长 1 保证所有格子都可达。

手动走一遍

数组长度 35 时，步长 3、13、23 都可能在两版出现，而 33 只属于‘任意尾数 3 整数’版。若末格 33 有高分且中间大多负分，从起点直接跳 33 会改变最优路径，因此不能把两版当同一题面。

Python 参考实现

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

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

"""Maximum path score with 1-step or ending-in-three jumps."""


def allowed_steps(length: int, prime_only: bool) -> list[int]:
    steps = [1]
    if length <= 3:
        return steps
    composite = [False] * length
    if prime_only:
        composite[0] = composite[1] = True
        for p in range(2, int((length - 1) ** 0.5) + 1):
            if not composite[p]:
                for multiple in range(p * p, length, p):
                    composite[multiple] = True
    for step in range(3, length, 10):
        if not prime_only or not composite[step]:
            steps.append(step)
    return steps


def maximum_jump_score(values: list[int], prime_only: bool) -> int:
    if not values:
        raise ValueError("at least one cell required")
    steps = allowed_steps(len(values), prime_only)
    dp = [float("-inf")] * len(values)
    dp[0] = values[0]
    for i in range(1, len(values)):
        dp[i] = values[i] + max(dp[i - step] for step in steps if step <= i)
    return int(dp[-1])

复杂度

设合法步长个数 S。筛质数上界 O(n log log n) 时间、O(n) 空间；DP 为 O(nS) 时间、O(n+S) 空间。尾数为 3 的候选约 n/10，直接转移最坏 O(n²)；大 n 时需问清约束再考虑更复杂的模 10 前缀最大值优化。

易错点与追问

容易失分的边界

• ‘尾数是 3’不自动意味着质数，33、63 等会区分版本；必须按当次 OA 文字确认。
• 贪心只选当前最大格分不成立，因为一个跳跃的落点影响后续可到达路径。
• 如果分数有负数，初始化未访问状态为 0 会错误地凭空开始路径；用负无穷表示未到达。

继续深挖

• 若还要输出路径，转移时记录最优前驱下标，从末格反向回溯。
• 若允许向左跳，递增下标 DP 不再适用；可能出现环，须重新约定重复访问及目标。