DP Solution


  • 0

    Just store all the jump lengths that can end up in each stone.

    var canCross = function(stones) {
        
        const sol = [ [ 0 ] ];
        for (let i = 1; i < stones.length; i++) {
            sol[i] = [];
            for (let j = i - 1; j >= 0; j--) {
                const needJump = stones[i] - stones[j];
                const jumps = sol[j];
                for (let k = 0; k < jumps.length; k++) {
                    if (Math.abs(jumps[k] - needJump) <= 1) {
                        sol[i].push(needJump);
                        break;
                    }
                }
            }
        }
        return sol[sol.length - 1].length > 0;
    };
    

Log in to reply
 

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