55. 跳跃游戏---自顶向下的dp

image.png

1：要理解回溯问题，直接画出二叉树，然后通过不断的剪枝来实现
dp数组的1代表该点肯定能到达最后节点，0代表还不确定是不是能到达最后节点，-1代表肯定无法到达，在代码中，如果看到1就返回true，代表肯定能到达
2：如果是0，那就需要遍历从该点的下一个节点到其最大跳动长度之间，递归调用dp(i),看这些点有没有是返回true的，如果返回true，那
dp[position]=1;
return true;
否则就会
dp[position]=-1;
return false;

image.png

class Solution {
    
    public boolean canJump(int[] nums) {
    int length=nums.length;
    int [] dp=new int[length];
    dp[nums.length-1]=1; 
    //最后一个元素肯定是通的
     boolean res=dp(0,dp,length,nums);
     return res;
    }
    public boolean dp(int position,int [] dp,int length,int [] nums){
        if(dp[position]==1){//1代表肯定是能到达最后元素
            return true;
        }
        if(dp[position]==-1){
            return false;
        }
        int maxjump=Math.min(position+nums[position],length);//保证不能跳出边界
        for(int i=position+1;i<=maxjump;i++){//遍历position+1到maxjump的点，因为有很多种情况
            boolean a=dp(i,dp,length,nums);
            if(a==true){
                dp[position]=1;
                return true;
            }
        }
        dp[position]=-1;
        return false;
    }
}