LeetCode刷题笔记——Greedy

55. Jump Game

没有get到思路，一开始使用动态规划的思路解决，这就是O(n^2)的时间复杂度，从后往前走，判断每一个格子是否可以到达末尾。
然后看了最快的思路的解法：

public class Solution {
    public boolean canJump(int[] nums) {
        int lastPos = nums.length - 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (i + nums[i] >= lastPos) {
                lastPos = i;
            }
        }
        return lastPos == 0;
    }
}

这个是O(n)的解法。lastpos表示上一次可以到达末尾的goodpoint，如果自己能jump到这个最近的goodpoint，那么自己也是goodpoint了。然后结束之后只需要判断最近的goodpoint是不是0就可以。