55. 跳跃游戏---自底向上的dp

image.png

自顶向下算法是基于从左往右的推导，自底向上算法是基于从右往左的推导
不用递归调用就可以实现
1：第一层for循环，从倒数第二个数开始遍历
2：第二层for循环，遍历第i个点能到达的所有点，如果这些点的dp有为1的，就直接将dp[i]=1，返回true
在最后只去返回dp[0]即可

image.png

class Solution {
    
    public boolean canJump(int[] nums) {
    int length=nums.length;
    int [] dp=new int[length];
    dp[nums.length-1]=1; 
    for(int i=length-2;i>=0;i--){
        int maxJump=Math.min(i+nums[i],length);
        for(int j=i+1;j<=maxJump;j++){
            if(dp[j]==1){
                dp[i]=1;
                break;
            }
        }
    }
    if(dp[0]==1) return true;
    return false;
    }
}