/
     有n块石头分别在x轴的0，1，2….n-1位置
    一只青蛙在0处，想跳到n-1处，
     如果青蛙在第i块石头上，他能跳最大距离ai
    问是否能跳到
     初始化f[0]=false
     计算f[1]、f[2]、f[3]….f[n-1]
     返回f[n-1]
     eg:
    输入：a=[3,3,1,1,4] 输出：True
     输入：a=[3,2,1,0,4] 输出：False
    时间复杂度O(N^2) 空间复杂度O(N)
    /

    1. //存在型动态规划
    2. public class Solution2 {
    3.     public static boolean canJump(int[] A){
    4.         if(A==null||A.length==0)
    5.             return false;
    6.         int n=A.length;
    7.         boolean[] f=new boolean[n];//建立辅助空间
    8.         f[0]=true;
    10.         for(int i=1;i<n;i++){
    11.             f[i]=false;//初始化为false
    12.             for(int j=0;j<i;j++) {//从第0个石头开始
    13.                 if( f[j] && j+A[j]>=i ) {//跳最大距离ai
    14.                     f[i] = true;
    15.                     break;
    16.                 }
    17.             }
    18.         }
    19.         return f[n-1];//下标从0开始
    20.     }
    22.     public static void main(String[] args) {
    23.         int[] A={3,3,1,1,4};//n=A.length
    24.         System.out.println(canJump(A));
    25.     }
    26. }