Java DP solution without map


  • 0
    H

    Just use a DP array to track the max units of the last jump that can possibly reach to each stone. Scan each stone in order, try jump from it towards the end as far as possible, while updating the DP for each stone that can be reached.

    public boolean canCross(int[] stones) {
            int n = stones.length;
            // DP tracks the max units of last jump to reach each stone
            int[] dp = new int[n];
            
            for (int i = 0; i < n; i++) {
                // Skip if no previous jumps can reach this stone
                if (i > 0 && dp[i] == 0) continue;
                
                // Greedy try to jump forward as far as possible
                for (int j = i + 1; j < n; j++) {
                    int gap = stones[j] - stones[i];
                    if (gap > dp[i] + 1) break;      // Too far to reach
    
                    if (gap == dp[i] - 1 || gap == dp[i] || gap == dp[i] + 1) {
                        dp[j] = Math.max(gap, dp[j]);     // Update DP if a stone is reachable
                    }
                }
            }
            return dp[n - 1] > 0;
        }
    

  • 0
    J

    [0,1,3,6,10, 13, 15, 18]

    it should be true, yours return false


  • 0
    H

    @jordandong said in Java DP solution without map:

    [0,1,3,6,10, 13, 15, 18]

    Nice catch! Your test case should be added by leetcode. I'll fix my bug.


  • 0
    K

    I think your algorithm is more like a greedy not DP.


  • 0
    K

    I'm still confused about your dp state, why this kind of state can work out the right answer? Could you give some more explanation? Thanks.


  • 1
    H

    @kad0108go Actually I found a bug in my solution posted above. It does not pass the test case like this [0,1,3,6,10, 13, 15, 18], which seems not included in the OJ test suite for this question. Now I do not think my solution is a valid solution any more, since we cannot track only the max jump. We'd have to keep all possible jump distances for each stone, so a map would be needed.


  • 0

    @jordandong Thanks, I have added your test case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.