题意概述

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

方法一:动态规划

思路与具体做法

  • dp[i]表示到达第i个格子至少需要的步数
  • 循环2到n,找每个位置i的最远前驱j
  • 并跟新dp数组dp[i]=dp[j]+1; alt
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(n2)O(n^2),n是数组长度,用到了双重循环,最坏情况下a数组元素全1,需要遍历所有元素
  • 空间复杂度:O(1)O(1),未用到额外空间。