Best Score With Bounded Hops
Medium1-D Dynamic Programming
Problem
A board game track has cells with points points[i] (possibly negative). You start on cell 0 and must finish on the last cell. From cell i you may hop to any cell from i + 1 to i + k.
Your score is the sum of the points of every cell you land on, including the first and the last. Return the maximum score.
Example 1
- Input:
- points = [1, -2, -7, 4, -3, 5], k = 2
- Output:
- 8
Land on 0, 1, 3, 5: 1 - 2 + 4 + 5 = 8 (cell 2 at -7 is skipped, cell 4 at -3 is skipped).
Example 2
- Input:
- points = [3, -1, -1, -1, 2], k = 1
- Output:
- 2
With k = 1 every cell must be visited.
Constraints
- 1 ≤ points.length ≤ 10^5
- 1 ≤ k ≤ 10^5
- -10^4 ≤ points[i] ≤ 10^4
Hint
Show the first hint
Let best[i] be the best score of a route that ends on cell i.
Walkthrough
How to approach it
01Clarify before coding
- Are the first and last cells always counted? Yes, you land on both.
- Can points be negative? Yes, so skipping cells is often useful, but you cannot skip more than k - 1 in a row.
- How large are n and k? Both up to 10^5, so an O(n·k) scan is too slow.
02Brute force
DP with a plain inner loop: best[i] = points[i] + max(best[j]) for j in [i - k, i - 1].
Cost: O(n · k): up to 10^10 operations when both are 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.