55. 跳跃游戏1

方法1：动态规划

dp数组的含义：dp[i]表示在当前位置i时，能到达的最远距离（的索引）（前提是能到达当前位置）
状态转移方程：当能到达当前位置时，dp[i] = max(dp[i - 1], i + nums[i])。也就是前一个位置能到达的最远距离和当前位置能到达的最远距离的最大值

class Solution(object):
    def canJump(self, nums):
        n=len(nums)
        dp=[0]*n # 构建dp数组
        dp[0]=nums[0]
        for i in range(1,n):
            if dp[i-1]<i: # 到达不了当前位置
                return False
            else: # 可以到达i处，可以进行状态转移
                dp[i] = max(dp[i - 1], i + nums[i])
        return True

方法2：贪心算法

贪心作为一种特殊的动态规划，通常也是用于求最值。在本题，函数的结果并不需要返回dp数组中的值。所以可以用一个全局变量cur来代替dp数组的含义。为了求能到达的最远距离，我们只要在遍历过程中更新并维护这个cur距离即可。

cur的含义：表示遍历到当前位置i时，能到达的最远距离（的索引）（前提是能到达当前位置）
在for循环中，每一步都计算一下从当前位置最远能够跳到哪里，然后和一个全局最优的最远位置cur做对比，通过每一步的最优解，更新全局最优解，这就是贪心

class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        cur=0
        for i in range(len(nums)):
            if cur<i: # 当前的“能量”不足以跳到i处
                return False
            cur = max(cur, i + nums[i]) # 可以跳到i处，这时更新当前“能量”
        return True

45. 跳跃游戏2

方法1：动态规划

因为该题属于求极值问题，所以可以用动态规划的方法解决

dp[i]数组的含义：到达位置i时，跳跃的最小次数
base case：先将dp数组设为最大值float("inf"),dp[0]=0（第0个位置不用跳）
状态转移方程：从i前面的位置开始顺序遍历，遍历过程中，如果i前面的某一个位置k处的“能量”能跳到i处（nums[k]+k>=i）,则比较已保存的dp[i]和dp[k]+1，取二者的最小值（始终使dp[i]保持最小值）

类似的题目有300. 最长递增子序列,也是在两层for循环中，用if条件进行判断，从而（通过状态转移来）更新dp数组

class Solution(object):
    def jump(self, nums):
        dp = [float("inf") for _ in range(len(nums))]
        dp[0]=0
        for i in range(1, len(nums)):
            for k in range(i):
                if nums[k]+k >= i :
                    dp[i]=min(dp[i],dp[k]+1)
        return dp[-1]

using namespace std;
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(nums[j]+j>=i){
                    dp[i]=min(dp[i],dp[j]+1);
                }
            }
        }
        return dp.back();
    }
};

方法2：贪心算法（供参考）

在for循环中，farthest表示（从当前第i个位置）能到达最远距离的下标

我们不需要【递归地】计算出所有选择的具体结果然后比较求最值，而只需要做出那个最有【潜力】，看起来最优的选择即可。
i 和 end 标记了可以选择的跳跃步数，farthest 标记了所有选择 [i..end] 中能够跳到的最远距离，step记录了跳跃次数。
当i到达end处时，把end更新为更远的farthest，步数+1

class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        farthest,end,step=0,0,0
        for i in range(len(nums)-1):
            farthest=max(farthest,i+nums[i])
            if i==end:
                end=farthest
                step+=1
        return step