A simple c++ dp solution with O(n) time


  • 1
    B
    class Solution {
    public:
        bool canJump(int A[], int n) {
            
            int dp[n];
            int i;
            dp[0] = A[0];
            
            if ( n == 1 )
                return true;
                
            if ( A[0] == 0 )
                return false;
                
            for ( i = 1; i < n; i++ ) {
                
                dp[i] = ( dp[i-1]-1 > A[i] ? dp[i-1]-1 : A[i] );
                if ( dp[i] >= 0 && i == n-1)
                    return true;
                else if ( dp[i] == 0 && i < n-1 )
                    break;
            }
            return false;
        }
    };

Log in to reply
 

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