跳跃游戏(一)

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i< n;i++) {
                arr[i] = in.nextInt();
            }
            boolean b = dfs(arr);
            System.out.println(b);
        }
    }
    
    // dp 记录能到达的最大的index
    // 时间复杂度为n
    public static boolean dp2(int[] arr) {
        int n = arr.length;
        int dp = arr[0];
        for (int i = 1; i < n && i <= dp ; i++) {
            dp = Math.max(dp, arr[i] + i);
        }
        return dp >= n -1;
    }
    
    // 时间和arr元素的大小相关，当arr元素较小时，时间复杂度为O(n) = n
    public static boolean dp1(int[] arr) {
        int n = arr.length;
        boolean[] dp = new boolean[arr.length];
        dp[0] = true; 
        for (int i = 0; i<n; i++) {
            if (dp[i]) {
                for (int j= i+1; j <n && j <= i + arr[i]; j++) {
                    dp[j] = true;
                    if (j == arr.length -1) return true;
                }
            } else {
                break;
            }
        }
        return dp[arr.length -1];
    }
    
    // timeout
    // O(n) = n^2
    public static boolean dp3(int[] arr) {
        boolean[] dp = new boolean[arr.length];
        dp[0] = true;
        for (int i = 1; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                dp[i] = dp[j] && (i-j<=arr[j]);
                if (dp[i]) break;
            }
        }
        return dp[arr.length-1];
    }
    
    public static boolean dfs(int[] arr) {
        
        return _dfs(arr, 0);
    }
    
     public static boolean _dfs(int[] arr, int idx) {
        if (idx == arr.length - 1) return true;
        int step = arr[idx];
         for (int i=idx+1; i<=idx+step&&i<arr.length;i++) {
             if (_dfs(arr, i)) return true;
         }
        return false;
    }
    
    
    
    
    // out of memory
    public static boolean bfs(int[] arr) {
        int len = arr.length;
        LinkedList<Integer> list = new LinkedList<>();
        list.add(0);
         
        boolean found = false;
        while (!list.isEmpty()) {
            int idx = list.removeFirst();
            if (idx == len - 1) return true;
            int step = arr[idx];
            for (int i = idx+1; i <= idx + step; i++) {
                list.add(i);
            }
        }
        
        return false;
    }
    
    
}