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

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

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

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

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

那么它的递推公式就是

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

结合成代码

   /**     * @param Integer[] $nums     * @return Boolean     */    function canJump($nums) {         $dp[0]=true;//0的位置当然可以到        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]; }

未经允许不得转载:PHP100中文网 - 中国第一档PHP资源分享门户 » Leetcode基础刷题之PHP解析(55. Jump Game)

赞 (0) 打赏

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏