Leetcode基础刷题之PHP解析(55. Jump Game)


 2019-7-15 星期一 开始吧

明天开始上班,慢慢的再下班回家以后抽一点时间出来刷题了。

Leetcode基础刷题之PHP解析(49. Group Anagrams)


5de558ce15a3c9334bb8186dcb355af8.png


给定一个非负的整数数组,数组索引上的数表示每次最大可以跳跃的步数,判断这组数组是否能跳跃到数组最后的索引位置,当然超过的也算。



这道题可以利用动态规划的思想解决,对于判断当前索引处能不能到达,可以定义为

$dp[$i]=true //表示i位置可到达

那么它的递推公式就是

判断$i-1(暂且称为$j)位置是否可到达 && $nums[$j]位置的值要大于 $i-$j

结合成代码

  /**
     * @param Integer[] $nums
     * @return Boolean
     */
    function canJump($nums) {
       $dp[0]=true;
        for($i=1;$i<count($nums);$i++){
            for($j=$i-1;$j>-1;$j--){
                if($dp[$j] && $nums[$j]>=($i-$j)){
                    $dp[$i]=true;
                    break;
                }
            }
        }
        
        return $dp[count($nums)-1];
  
}

Github整理地址:https://github.com/wuqinqiang/leetcode-php


Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode PHP题解--D103 447. Number of Boomerangs

>> 下一篇: Leetcode PHP题解--D104 167. Two Sum II - Input array is sorted