#55 Jump Game
题目地址：https://leetcode.com/problems/jump-game/
标准的动态规划问题，其实最好先用蠢方法（递归）自己试一遍，推导出递推公式，然后转化为for循环。
动态规划 (时间复杂度O(n^2))
把数组内的每一个位置标记为”GOOD"或者"BAD"，前者代表可以从此处直接抵达终点，后者代表不可以。
Base case是确定的：数组中的最后一个位置必定是GOOD。那么目标就变成了从后面的位置往前推。
前面位置是否为GOOD的判断规则：如果从这个位置往后跳能到达任何GOOD位置，那么这个位置也是GOOD，否则为BAD。所谓“往后跳“，就是指这个位置能向右达到的最远距离。
得到递推公式就很简单了，可以用DP做。代码如下：
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums.empty()) return true;
// 0: Unknown, 1: Good, -1: Bad
vector<int> canJumpFrom(nums.size(), 0);
canJumpFrom.at(nums.size()-1) = 1;
for(int ind = nums.size()-2; ind >= 0; --ind){
int furtherestPoint = min(ind+nums.at(ind), (int)nums.size()-1);
for(int pos = furtherestPoint; pos > ind; --pos){
if(canJumpFrom.at(pos) == 1){
canJumpFrom.at(ind) = 1;
break;
}
canJumpFrom.at(ind) = -1;
}
}
if(canJumpFrom.at(0) == 1)
return true;
else
return false;
}
};
这个方法打败了22.2%的人。考虑到能做出这个题至少都是用动态规划做的，我感觉我写的还可以。
时间复杂度为O(n^2)，空间复杂度为O(n)，用来存GOOD和BAD的数组占用了一定的空间。
贪婪算法（时间复杂度O(n)）
我对贪婪算法(Greedy Algorithm)知之甚少，这里只能说是依葫芦画瓢；总体思路依然是从后往前搜索，如果当前的位置为GOOD（能抵达终点），就把当前的位置作为新的终点。代码如下：
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums.empty()) return true;
int boundary = nums.size()-1;
for(int ind = nums.size()-1; ind >=0; ind--){
if(ind + nums.at(ind) >= boundary)
boundary = ind;
}
return boundary == 0;
}
};
时间复杂度为O(n), 空间复杂度为O(1)。这种算法甚至不需要保存GOOD/BAD数组，我只要能达到起点即可。这么说倒是有点像“倒着走迷宫”的思路。
#45 Jump Game II
问题地址：https://leetcode.com/problems/jump-game-ii/
不愧是Hard，我基本快缴械投降了。难还是难在很难想出Dynamic Programming的递推公式来。
初见-Dynamic Programming(时间复杂度O(n^2))
思路倒是很简单，从起点开始不断增长数组的长度，抵达终点的方法有两种：一步到位，或者从走中间。而当把起点也当成是“中间”的时候，这两种方法其实也可以合并为一种。走“中间”的步数就是走到中间所需步数再+1。
递推公式如下：
具体实现：
class Solution {
public:
int jump(vector<int>& nums) {
vector<int> jumpNums(nums.size(), INT_MAX);
jumpNums.at(0) = 0;
for(int index = 0; index < nums.size(); ++index){
for(int secInd = 0; secInd < index; secInd++){
if(secInd + nums.at(secInd) >= index)
jumpNums.at(index) = min(jumpNums.at(index), jumpNums.at(secInd) + 1);
}
}
return *jumpNums.rbegin();
}
};
时间复杂度O(n^2)，空间复杂度O(n)。
