跳跃游戏

难度：中等

题目描述

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例1

输入：nums = [2,3,1,1,4] 输出：true

示例2

输入：nums = [3,2,1,0,4] 输出：false

题解

采用动态规划，具体步骤如下：

• 定义 $len$ 为数组长度，$maxLength$ 为当前所能到达的最大下标
• 进行循环，当 $i <len$ && $maxLength<n-1$ 时循环继续
• 如果下标 $i>maxLength$ 时，说明无法达到目标下标，返回 $false$
• $maxLength$ 变为 $maxLength,nums[i]+i$的最大值
• 最后返回 $true$

想法代码

class Solution
{
    public static void Main(String[] args)
    {
        int[] nums = { 2, 3, 1, 1, 4 };
        Solution solution = new Solution();
        bool res = solution.CanJump(nums);
        Console.WriteLine(res);
    }

    public bool CanJump(int[] nums)
    {
        int len = nums.Length;
        int maxLength = 0;
        for (int i = 0; i < len && maxLength < len - 1; i++)
        {
            if (i > maxLength)
            {
                return false;
            }
            maxLength = Math.Max(maxLength, nums[i] + i);
        }
        return true;
    }
}