这个题我一开始想到的就是动态规划,但其实发现这个方法不是优法,因为用到了两层循环,时间复杂度大.
但是确实这题确实有动态规划的思想 代码贴在这里
class Solution {
public:
int jump(vector& nums) {
vector dp(nums.size(), INT_MAX);
dp[0] = 0;
//dp[i]表示从初始位置到第i个位置的最少跳跃次数
for (int i = 0; i < nums.size(); i++) {
for (int j = 1; j <= nums[i]; j++) {
if (i + j < nums.size()) {
dp[i + j] = min(dp[i + j], dp[i] + 1);
}
}
}
return dp[nums.size() – 1];
}
};
这题的另一个方法更直观 可以使用贪心策略:
每次找到可到达的最远位置，就可以在线性时间内得到最少的跳跃次数
例如，对于数组 [2,3,1,2,4,2,3]，初始位置是下标 0，从下标 0 出发，最远可到达下标 2。下标 0 可到达的位置中，下标 1 的值是 3，从下标 1 出发可以达到更远的位置，因此第一步到达下标 1。
从下标 1 出发，最远可到达下标 4。下标 1 可到达的位置中，下标 4 的值是 4 ，从下标 4 出发可以达到更远的位置，因此第二步到达下标 4。
class Solution {
public:
int jump(std::vector& nums) {
int jumps = 0, currentEnd = 0, farthest = 0;
for (int i = 0; i < nums.size() - 1; i++) {
// 更新能达到的最远距离
farthest = std::max(farthest, i + nums[i]);
// 如果我们到了当前跳跃的边界，就增加跳跃次数
if (i == currentEnd) {
jumps++;
currentEnd = farthest; // 更新当前边界
}
}
return jumps;
}};