题解 | #跳跃游戏(一)#

用dp[i]表示在第i个位置，能跳的最远距离。
所以状态转移方程就是：
    dp[i] = max( dp[i-1],i+nums[i] )
要么前一个位置跳的比当前位置远，要么现在这位置跳的远
需要注意边界条件，当前位置最远能跳到的位置如果就是自己本身，那么就是无法跳到结尾的情况
最终就是判断dp[i]是否有大于或者等于 numsLen - 1
#include<stdbool.h>
int max( const int a , const int b )
{
    return a>b?a:b;
}


bool canJump(int* nums, int numsLen ) 
{
    // write code here
    if( numsLen == 1 ) return true;
    if( !nums[0] ) return false;
     
    int dp[numsLen];
    memset( dp,0,sizeof(dp) );
    
    dp[0] = nums[0];
    
    for( int i = 1; i < numsLen; ++i )
    {
        if( dp[i-1] < i ) return false;      //当前一个位置能跳的最远距离没有当前位置远的时候，就是无法跳到最后的情况
        dp[i] = max( dp[i-1], i+nums[i] );
        if( dp[i]  >=  numsLen-1  ) return true;
    }
    
    return false;
    
}