Easy to understand DP solution with explanation


  • 0
    C

    f[i] represents all the possible jump-lengths to arrive at store i.
    Given stone i and stone j (j>i), their distance is dis = stones[j] - stones[i].
    If f[i] contains a jump-length that equals to dis or dis-1 or dis+1, then the frog can jump from stone i to stone j.
    In that case, we should add 'dis' into f[j].
    Finally, if f[stones.length-1] has at least 1 element, it means the frog can reach the end.

    var canCross = function(stones) {
      let f = [];
      stones.forEach((s,i) => {f[i] = new Set()});
      f[0] = new Set([0]);
      for (let i=0;i<stones.length;i++){
        for (let j=i+1;j<stones.length;j++){
          let dis = stones[j] - stones[i];
          if (f[i].has(dis) || f[i].has(dis-1) || f[i].has(dis+1)){
            f[j].add(dis);
          }
        }
      }
      return f[stones.length-1].size > 0;
    };

Log in to reply
 

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