45. Jump Game II

greedy O(n) time O(1) space
相当于BFS一棵树
last就是当前层所能达到的最远位置（可以覆盖的地方）
curr_max是当前位置能达到的最远位置
题解比较清楚
0 1 2 3 4 i
2 3 1 1 4 nums[i]
2 4 3 4 8 i + nums[i]
0 2 2 4 4 last
2 4 4 4 8 curr_max
{0(2)} –> {1(4) 2(3)} –> {3(4) 4(8)}
意思是最开始在0，不跳的话只能到0，如果想跳到1以后需要跳一次，这一次最远跳到2，然后如果想再跳到3以后需要再跳一次，这一次至少跳到4（最远跳到8但是不需要了），因为4已经达到最远点，跳出循环

class Solution:
    def jump(self, nums: List[int]) -> int:
        possible = curr = res = 0
        n = len(nums)
        for i in range(n):
            if curr >= n - 1:
                break
            if curr < i:
                curr = possible
                res += 1
            possible = max(possible, i + nums[i])
        return res

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        int last = 0;
        int curr_max = 0;
        int cnt = 0;
        for (int i = 0; i < n && last < n - 1; ++i) { // last < n - 1是一个优化，因为last达到n - 1就说明cnt已经够了
            if (i > last) { // bfs应该先更新，表示必须要jump一次才能达到当前的i
                last = curr_max;
                ++cnt;
            }
            curr_max = max(curr_max, i + nums[i]); // bfs应该后『遍历』如果颠倒顺序last少更新一次
        }
        return cnt;
    }
};

dp O(n²) time O(n) space TLE
dp[i]表示达到i所需要的最少步数
求dp[i]需要查询dp[j] where 0 <= j < i，然后+1
dp[0]肯定为0

class Solution {
public:
    int jump(vector<int>& nums) {
        int n(nums.size());
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for (int i(1); i < n; ++i) {
            for (int j(0); j < i; ++j) {
                if (j + nums[j] >= i)
                    dp[i] = min(dp[i], dp[j] + 1);
            }
        }
        return dp.back();
    }
};