DYNAMIC PROGRAMMING › 1D ARRAYS

Frog Jump

A frog can jump 1 or 2 steps at a time. Each jump has a cost, and the goal is to reach the end with the minimum total cost.

Time

O(N)

Space

O(N) or O(1)

Key Principle 1

At each stone, compare the cost of coming from the previous one or two positions.

Key Principle 2

This is a minimum-cost DP rather than a counting DP.

Key Principle 3

The first two stones form the base cases for the recurrence.

Key Principle 4

The same pattern extends to variable jump lengths and path-cost problems.

Loading Lab...