# Java DP solution without map

• 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,1,3,6,10, 13, 15, 18]

it should be true, yours return false

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

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

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

• 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.

• @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.