[55] Jump Game

其實真的想不太出來Orz
是不是被它分類在DP給限制住了呢 Orz
笨笨的QQ

給一個array 存大於等於0的數值,
每個數字代表最多可以前進幾格,
問能不能走到最後一格

Jump Game
bool canJump(int* nums, int numsSize) {
    if (numsSize == 1)
        return true;
    else if (nums[0] == 0)
        return false;


    int *check = malloc(sizeof(int)*numsSize);
    memset(check,0,sizeof(int)*numsSize);
    int i,j;
    for(i=0;i<numsSize-1;i++)
    {
        for (j=nums[i]; j>0; j--)
            if(i+j <numsSize)
                check[i+j]++;
    }
    for(i=1;i<numsSize;i++)
    {
        if (check[i]==0)
            return false;
    }
    return (check[numsSize-1]>0)?true:false;
   
}
結果超級慢的哈哈哈(欲哭無淚)
好像只要這樣就好了QQ
bool canJump(int* nums, int numsSize) {
    if (numsSize == 1)
        return true;

    int i,maxJump=0;
    for(i==0;i<numsSize-1;i++)
    {
        if(i>maxJump)
            return false;
        maxJump = (maxJump > (nums[i] + i))? maxJump: (nums[i] + i);
    }
    return (maxJump>=numsSize-1)?true:false;
}