leetcode 45. Jump Game II

45. Jump Game II 55. Jump Game

分析

诚实地说，这两道题对我来说有相当难度，因为用DP，也就是复杂度为O(n^2)的算法居然ac不了，又因为我不太熟悉贪心，所以这两道题花了很多时间。

DP

这道题是DP问题新的模型。它问你从起始点是否可以到达终点，我们就可以想假如可以的话，需要满足什么条件，那当然是他所能及的范围内，存在能达到起始点的点了。于是我们就能想到要保存的状态就是各点是否能达到终点。

至于最少步数的话，要保存的状态就是该点到达终点所需的最少步数，解法类似。

Greedy

找到贪心解法的一个方法就是对DP解法重新审视，然后找到方法。

还是从起点出发，我们想，我们需要确认所有其所及范围内的点吗？不需要，如果我们能达到离其最近的goodpoint的话，我们也就可以达到终点了。

BFS

这个问题还是非常精妙的。

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size(), step = 0, start = 0, end = 0;
        while (end < n - 1) {
            step++; 
			int maxend = end + 1;
			for (int i = start; i <= end; i++) {
                if (i + nums[i] >= n - 1) return step;
				maxend = max(maxend, i + nums[i]);
			}
            start = end + 1;
            end = maxend;
        }
		return step;
    }
};

BFS 解法

start和end是用来记录当前level的range的，复杂度来看，应当是O(n)。