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

 2019-7-15 星期一 开始吧

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

上一题链接Leetcode基础刷题之PHP解析(49. Group Anagrams)

题目描述

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

题目分析

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

$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