跳盒子

'''
 Welcome to vivo !
'''
# leetcode 原题45   输出要改一下
#leetcode保证能跳到最后一个位置，这里不一定
def solution(step_list):
    n=len(step_list)
    max_num=0
    cnt=0
    end=0
    for i in range(n-1):
        if i<=max_num:
            max_num=max(max_num,i+step_list[i])
            #if max_num>=n-1
            if i==end:
                end=max_num
                cnt=cnt+1
    return cnt if max_num>=n-1 else -1

step_list = [int(i) for i in input().split()]
print(solution(step_list))

 private static int solution(int[] input) {


        if(input.length==1){
            //如果只有一个盒子，那么起点即为终点，无需跳跃
            return 0;
        }
        if(input.length>1&&input[0]==0){
            //如果不只一个盒子，那么肯定需要跳动。但是起点位置能跳跃的距离为0
            // 那么肯定到不了终点
            return -1;
        }
        //下面的代码处理需要跳动才能到达终点的情况
        int[] dp=new int[input.length];

        for (int i=0;i<input.length;i++){
            //计算能够到达最右的盒子
            int range=Math.min(input.length-1,i+input[i]);
            for (int j=i+1;j<=range;j++){
                if(dp[j]==0){
                    dp[j]=dp[i]+1;
                }
            }
        }
        int ret=dp[input.length-1];
        //需要跳动的次数至少大于0，结果出现跳动0次，说明不可达，返回-1
        return ret==0?-1:ret;

    }

#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
#include <limits.h>

using namespace std;
bool flag;
int solution(int a[], int N, int depth)
{
    int min_depth = INT_MAX;
    if(N <= 0){
        return depth;
    }
    if(a[0] == 0){
        return -1;
    }
    for(int i = N-1; i >= 0; i--){
        if(a[i]+i >= N){
            int temp = solution(a,i,depth+1);
            min_depth = min(min_depth, temp);
            flag = true;
        }
    }
    if(flag){
        return min_depth;
    }else{
        return -1;
    }
}

int main()
{
	string str("");
	getline(cin, str);
	int a[2000];
	int i = 0;
	char *p;
	int count = 0;

	const char* strs = str.c_str();
	p = strtok((char *)strs, " ");
	while(p)
	{
		a[i] = atoi(p);
		count++;
		p = strtok(NULL, " ");
		i++;
		if(i >= 2000)
			break;
	}
    flag = false;
	int num = solution(a, count-1, 0);
	cout << num << endl;
	return 0;
}

//i+a[i]即i位置最多可跳至i+a[i]位置，最后一个位置为N-1，假如我们想跳至位置j，
//我们只需在j前面中找出不小于j的数就代表可跳至j，取最前面的那一个不小于j的就
//可得到最小步数。
int solution(int a[], int N)
{

        // TODO Write your code here
    vector<int> v;
    for(int i = 0;i < N;i++){
        v.push_back(i+a[i]);
    }
    if(v.size() == 1)
        return 0;
    int tmp = N-1;
    int step = 0;
    bool bark = false;
    for(int i = 0;i < tmp;i++){
        if(v[i] >= tmp){
            step++;
            if(i != 0){
                tmp = i;
                i = -1;  
            }
            else{
                bark = true;
                break;
            }
        }
    }
    return (bark)?step:-1;
        
}

//一大堆if  else 的**算法

private static int solution(int[] input) {
        
        // TODO Write your code here
        if(input.length==1){
            //如果只有一个盒子，那么起点即为终点，无需跳跃
            return 0;
        }
           
        int step = 0;
        int end = input[0];
        int big = input[0];
        for(int i =0;i<input.length;i++){
            if(end>=i){
                if(big<input[i]+i){
                    big = input[i]+i;
                }
            }else if(end<i){
                step++;
                end = big;
                if(end<i){
                    return -1;
                }
                big = input[i]+i;
            }
            if(end>=input.length-1){
                step++;
                break;
            }
            
            
        }
        
        
        
        
        
        
        return step;
    }

def canJump(nums):
    steps = 0
    max_Jump = 0
    for i in range(len(nums)-1):
        if i > max_Jump:
            return -1
        if max_Jump < i + nums[i]:
            steps +=1
            max_Jump = i + nums[i]
    if max_Jump >= len(nums) - 1: 
        return steps
    else:
        return -1

step_list = [int(i) for i in input().split()]
print(canJump(step_list))

还是使用了递归的情况，把所有情况都考虑了一遍。后来想到，其实可以在times > min_times的时候就终止
此次递归。

void getResult(int a[], int start, int end,int times,int &min_times) {
    if (start < end && a[start] == 0) {
        return; // 不符合条件
    }
    if (start >= end) {
        if (times < min_times) { // 更新最小值
            min_times = times;
        }
        return;
    }
    for (int i = 1; i <= a[start]; i++) {
        getResult(a, start + i, end,times+1,min_times); // 迭代函数
    }
}
int solution(int a[], int N)
{
    int result = 0, min_times = N+1; // 设置不可能步数为初始值
    getResult(a, 0, N - 1,result,min_times);
    if(min_times > N) return -1;
    return min_times;
}

//递归(纯暴力)
       private static int solution(int[] input) {
            //len-1是终点，input[i]是在当前格子i,能够跳多远
            int len=input.length; 
            int ret=recursion(0,input[0],input, len);//从第0个格子开始起跳
            return ret==len?-1:ret;//[0,1,0,1,1,0,0,0]永远跳不到终点
        }
        //start是当前处在的位置
        //capacity是当前格子能跳多远input[start]
        //len是数组input的长度
        private static int recursion(int start,int capacity,int[] input,int len){
            if(start==len-1){//到达终点
                return 0;//从终点出发，需要多个步骤能到达目标，0步
            }
            int ans=len;
            for(int i=1;i<=capacity;i++){
                if(start+i<=len-1){//从当前格子跳出距离为i，不能超出终点
                    ans=Math.min(ans,1+recursion(start+i,input[start+i],input,len));
                }else{
                    break;//憋跳了
                }
                //选择不跳，可以等到下一次再跳，i++即可
            }
            return ans;
        }