Start learning free

LESSON 272 OF 347 · MEMOIZATION

Jump Game in C#: Iterative Dynamic Programming for Minimum Jumps

Practice O(n2) - DP Read the full explanation

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2.
             Jump 1 step from index 0 to 1, then 3 steps to the last index.

Note:

Convert the previous solution to an iterative one. Your algorithm should run in O(n^2) time and use O(n) extra space.

STEP 1 OF 6
    Ctrl + Enter to check

    C# · MEMOIZATION

    Jump Game in C#, explained

    Problem overview

    You start at index 0 of an array of non-negative integers. Each element is the maximum jump length from its position: from index i you can land on any index from i + 1 to i + nums[i]. The method Jump returns the minimum number of jumps needed to reach the last index.

    For [2, 3, 1, 1, 4] the answer is 2: one step to index 1, then three steps to the end.

    The lesson asks for an iterative version of the memoized recursion, still in O(n^2) time and O(n) extra space.

    Approach: fill a table from right to left

    The recursive solution defines the answer from index i in terms of answers from larger indices: it is one jump plus the best answer among the reachable cells. Since every answer depends only on cells to its right, you can compute them in a loop, starting at the end of the array and moving left, and no recursion or dictionary is needed.

    Let dp[i] be the minimum number of jumps from index i to the last index. Then:

    • dp[last] = 0, because you are already there.
    • dp[i] = min(1 + dp[j]) over every j from i + 1 to i + nums[i] that is inside the array.

    Going right to left guarantees that each dp[j] you read is already final. The answer is dp[0].

    On [2, 3, 1, 1, 4] the table starts as [5, 5, 5, 5, 0], where 5 is the placeholder "infinity". Then:

    • i = 3: only j = 4 is reachable, so dp[3] = 1 + 0 = 1.
    • i = 2: only j = 3, so dp[2] = 1 + 1 = 2.
    • i = 1: j is 2, 3 or 4, giving 3, 2 and 1, so dp[1] = 1.
    • i = 0: j is 1 or 2, giving 2 and 3, so dp[0] = 2.

    The final table is [2, 1, 2, 1, 0] and the method returns 2.

    Step by step

    1. Create the table as an int[] of length nums.Length. A new int array is filled with zeros, which would look like "zero jumps" for every cell, so set every entry except the last to nums.Length. No real path takes that many jumps (at most nums.Length - 1), so it works as infinity until a real path replaces it. The last entry can stay 0.
    2. State the base case explicitly with dp[nums.Length - 1] = 0. It is already 0, but writing it makes the logic readable.
    3. Loop right to left with i starting at nums.Length - 2 and decreasing while i >= 0. The last cell is skipped because it is the base case.
    4. Loop over the targets with j from i + 1 while j < nums.Length and j <= i + nums[i].
    5. Relax dp[i] with Math.Min(dp[i], 1 + dp[j]): a first jump to j costs one jump plus the best from j.
    6. Return dp[0] once both loops finish.

    The solution in C#

    class Solution {
    public int Jump(int[] nums) {
        int[] dp = new int[nums.Length];
        for (int i = 0; i < dp.Length - 1; ++i) {
            dp[i] = nums.Length;
        }
        dp[nums.Length - 1] = 0;
        for (int i = nums.Length - 2; i >= 0; --i) {
            for (int j = i + 1; j < nums.Length && j <= i + nums[i]; ++j) {
                dp[i] = Math.Min(dp[i], 1 + dp[j]);
            }
        }
        return dp[0];
    }
}

    C# details worth knowing

    • Arrays start zeroed. new int[n] gives you n zeros, so a "not computed" or "infinite" marker has to be written explicitly, as the first loop does. Array.Fill(dp, nums.Length) would fill the whole array in one call, and the lesson's loop plus the base-case line gets the same result.
    • Reusing the name i. The two outer for loops each declare their own i. That is legal in C# because each variable's scope ends with its loop. Declaring a second i while the first is still in scope would be a compile error.
    • Pre-decrement in the header. --i and i-- behave the same in a for update clause, because the value of the expression is not used.

    Complexity

    The outer loop runs about n times and the inner loop at most n - 1 times, so the time is O(n^2). The only extra storage is the dp array of n integers, so the space is O(n). Compared with the memoized recursion, the time is the same, but there are no recursive calls and no dictionary lookups, so there is no stack depth to worry about for long arrays.

    Edge cases and common mistakes

    • A one-element array. The outer loop starts at nums.Length - 2, which is -1, so it never runs and dp[0] is the base case, 0.
    • Looping left to right. Then dp[j] would still hold its placeholder when you read it, and the answers would be wrong.
    • Using int.MaxValue as infinity. The placeholder nums.Length is safe because 1 + dp[j] stays small. With int.MaxValue, that addition would overflow and wrap to a large negative number, silently breaking the minimum.
    • Leaving the zeros in place. If you skip the first loop, every unfilled entry looks like a free cell and Math.Min keeps 0 forever, so the method would report 0 for most inputs.
    • Ignoring the array end. Without j < nums.Length, a large nums[i] makes dp[j] throw IndexOutOfRangeException.
    • Unreachable end. For input like [1, 0, 1] the last index can't be reached, and this code returns nums.Length, here 3. The lesson assumes the end is reachable.

    Testing

    These results come from running the solution:

    • [2, 3, 1, 1, 4] returns 2.
    • [1, 1, 1, 1] returns 3.
    • [0] returns 0.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free