题意概述

• 给定一个长度为n的素组a
• ai表示从i这个位置开始最多能往后跳多少格
• 求从1开始最少需要跳几次就能到达第 n 个格子。

方法一：动态规划

思路与具体做法

• dp[i]表示到达第i个格子至少需要的步数
• 循环2到n，找每个位置i的最远前驱j
• 并跟新dp数组dp[i]=dp[j]+1;

class Solution {
public:
    int Jump(int n, vector<int>& A) {
    	int dp[n+1];
    	int j=0;
		for(int i=2;i<=n;i++){//对每个位置i
			while(j+A[j]<i)j++;//找i的最远前驱j
			dp[i]=dp[j]+1;//并跟新dp数组  
		} 
		return dp[n]; 
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n)O(n)$，指针j最多移动n-1次。
• 空间复杂度：$O(n)O(n)$,用到了长度为n+1的dp数组。

方法二：从后向前贪心(超时)

思路与具体做法

• 思路为从最后一个位置开始找最远前驱位置，然后以这个最远前驱做当前位置，不断迭代找当前位置的最远前驱，直至起点
• 具体做法为遍历i从1到n，以位置i和位置i所能到达的距离A[i]的和和当前位置cur做比较，如果i+A[i]>=cur，即选i做最远前驱可以到达cur，那么我们就选位置i做最远前驱，并令步数加一
• 反复迭代上面的过程，直到起点

class Solution {
public:
    int Jump(int n, vector<int>& A) {
    	int cur=n-1,ans=0;
    	while(cur>0){//从最后一个位置开始找最远前驱位置，然后以这个最远前驱做当前位置，不断迭代，直至起点 
			for(int i=0;i<n;i++){
				if(i+A[i]>=cur){//i+A[i]：从枚举位置所能到的最远位置 
					cur=i;ans++;//跟新最远前驱，并令步数加一 
					break; 
				}
			}	
		}
		return ans;
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O(n^2)O(n^2)$,n是数组长度，用到了双重循环，最坏情况下a数组元素全1，需要遍历所有元素
• 空间复杂度：$O(1)O(1)$，未用到额外空间。