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

第一种方法是DP函数通过递归加回溯，从0位置从前往后找出所有能够到达终点的路径，将结果累加到sum中，若能到达终点且sum>max就赋值给max，但是复杂度过大pass掉了。
第二种方法是通过从后向前的循环，找出能走通的每一个节点并进行累加，就是这么简单。。。。。。

#include <stdio.h>
int max = -1;
int  DP(int* array, int size, int jump, int idx, int sum) {
    if (idx == size - 1) {
        max = max > (sum + array[idx]) ? max : (sum + array[idx]);
        return 0;
    }
    if (idx >= size) {
        return 0;
    }
    for (int k = 1; k <= jump; k++) {
        if (idx < size) {
            DP(array, size, array[idx + k], idx + k, sum + array[idx]);
        } else {
            break;
        }
    }
    return 0;
}
int main() {
    int b,size;
    scanf("%d", &size);//size为数组长度
    int array[size], i = 0;
    while (scanf("%d", &b) != EOF) {
        array[i++] = b;
    }
    int len=size-1,pre,sum = 0;
    for(int k=size-1;k>=0;k--){//从尾巴开始向前推
        if(array[k]>=len-k){
            int temp=array[k];
            sum+=temp;
            len=k;
        }
        else{
            pre=sum+1;//与sum比较判断能否到达第一个点
        }
    }
    pre=pre>sum?-1:sum;
    printf("%d", pre);
    //fun(array, size, array[0], 0, sum);
    //printf("%d", max);
    return 0;
}