Relay Jump Squares Problem

Relay Jump Squares Problem — ExecCode Hard DSA Practice

Solve the Relay Jump Squares problem on ExecCode. Free online hard DSA practice in DP. Write and run code in Java, C++, Python — no signup required to run.

Problem description

You stand on stones 0..n-1. From stone j you may jump to a later stone i paying (i-j)^2 plus the landing fee arr[i]. Start already on stone 0 with cost 0 (you do not pay arr[0] again). Convex hull trick speeds the DP dp[i] = min_j dp[j] + (i-j)^2 + arr[i]. Return dp at the last stone. You are given: arr — landing fees, index = stone Return minimum cost to reach the last stone. From 0 you may jump directly to n-1 in one move.

Examples

Input {'arr': [0, 1, 2]}; Output 5. Input {'arr': [5]}; Output 0. Input {'arr': [0, 0]}; Output 1

Constraints

n >= 1 Jumps only forward

Practice Relay Jump Squares free on ExecCode. Browse DSA problems, topic map, and placement guides.