55. Jump Game

放せ.昨日は长い间放送していましたが、ビデオに保存されていませんでした.本当に涙しか出ませんでした.
最初は最後の和だけを見て、それからすべてのインデックスの時はもっと大きいものだけを見ます.

class Solution {
    public boolean canJump(int[] nums) {
        int total = 0;
        for (int i = 0; i < nums.length; i++) {
            total += nums[i];
            
            if (total < i) {
                return false;
            }
        }
        
        return true; 
    }
}

残りのコミット...
間違っています.
こうして頭の中の名前をかすめて….backtrakcing...

class Solution {
    public boolean canJump(int[] nums) {
        return helper(nums, 0);
    }
    
    public boolean helper(int[] nums, int cur) {
        if (cur == nums.length - 1) {
            return true;
        }
        
        int next = Math.min(cur + nums[cur], nums.length - 1);
        
        for (int i = cur + 1; i <= next; i++) {
            if (helper(nums, i)) {
                return true;
            }
        }
        
        return false;
    }
}

時間制限が見つかりました...ほほほ
コードが悪いと思ったので見てみましたが、これは愚かな時間の限界です~
遡るのは私には難しいですがこれは時間がかかる友人ではないようです…^^
運転時O(2^n)

enum Index {
    GOOD, BAD, UNKNOWN
}

public class Solution {
    public boolean canJump(int[] nums) {
        Index[] memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;

        for (int i = nums.length - 2; i >= 0; i--) {
            int furthestJump = Math.min(i + nums[i], nums.length - 1);
            for (int j = i + 1; j <= furthestJump; j++) {
                if (memo[j] == Index.GOOD) {
                    memo[i] = Index.GOOD;
                    break;
                }
            }
        }

        return memo[0] == Index.GOOD;
    }
}

解決策はbottom-up
Runtime: 242 ms, faster than 30.61% of Java online submissions for Jump Game.
Memory Usage: 40.6 MB, less than 90.76% of Java online submissions for Jump Game.