动态规划——跳跃游戏

动态规划——跳跃游戏

题目描述

https://www.nowcoder.com/practice/b7d9d79453bf43bf9594e91d24260605?tpId=101&tqId=33160&tPage=1&rp=1&ru=/ta/programmer-code-interview-guide&qru=/ta/programmer-code-interview-guide/question-ranking
给定数组arr，arr[i]==k代表可以从位置向右跳1~k个距离。比如，arr[2]==3,代表可以从位置2跳到位置3、位置4或位置5。如果从位置0出发，返回最少跳几次能跳到arr最后的位置上。
输入描述
输出包括两行，第一行一个整数n(1≤n≤1e5)，代表arr数组长度，第二行n个整数代表数组arri。
输出描述:
输出一个整数，代表最少跳的次数。

输入 复制
6
3 2 3 1 1 4
输出 复制
2
说明
arr[0]==3，选择跳到位置2，arr[2]==3,可以跳到最后的位置。所以返回2。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        String[] s=br.readLine().split(" ");
        int[] arr=new int[n];
        int max = 0;
        for(int i=0;i<n;++i){
            arr[i]=Integer.parseInt(s[i]);
            if(arr[i]>max) {
                max=arr[i];
            }
        }
        int count=jump(max,arr,n-1);
        System.out.println(count);
    }
    public static int jump(final int max,int[] arr,int end){
        if(end==0)
            return 0;
        int pos=end-max<=0?0:end-max;
        while(arr[pos]+pos<end) {
            pos++;
        }
        return 1+jump(max,arr,pos);
    }
}