C# solution: dp with explanation


  • 0
    B

    We want to see whether the max step can reach to the end.

    Math.Max( preMaxStep - 1 (because the pre max step needs to step 1 to the current) , cur step)

    For example:
    [2, 3, 1, 1, 4]

    Index: 0 only 2 maxStep = 2
    Index: 1 Max(2 - 1, 3) maxStep = 3
    Index: 2 Max(3 - 1, 1) maxStep = 2
    Index: 3 Max(2 - 1, 1) maxStep = 1
    Index: 4 Max(1 - 1, 4) maxStep = 4

    reach to the end, so return true

    public class Solution 
    {
        public bool CanJump(int[] nums) 
        {
            if (nums.Length == 0) return false;
            if (nums.Length == 1) return true;
    
            var preMax = nums[0];
            
            if (preMax == 0) return false;
    
            for (int i = 1; i < nums.Length; i++)
            {
                var cur = Math.Max(preMax - 1, nums[i]);
    
                if (cur == 0)
                {
                    if (i == nums.Length - 1) return true;
                    else                      return false;
                }
    
                preMax = cur;
            }
    
            return true;
        }
    }
    

Log in to reply
 

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