动态规划——跳跃游戏
题目描述
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); } }