简介
本文主要介绍几个类似爬楼梯的问题，即用户可以跳跃，然后问能否到达终点或者到达终点有多少种方法。
爬楼梯
楼梯总共有 n 步台阶，每次可以爬 1 步或者 2 步。问爬到 n 步台阶这里有多少种方法？熟悉的人一看就是
动态规划问题：
F(n) = F(n-1) + F(n-2)
这个序列实际就是斐波那契数列。也有公式可以直接计算最终的结果。
Jump Game I
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
class Solution {
public:
bool canJump(vector<int>& nums) {
int max_end = 0;
int length = nums.size();
for (int i = 0; i < length; ++i) {
// cout << "max_end: " << max_end << endl;
// if (i < max_end && nums[i] == 0) continue;
if(i > max_end) return false;
max_end = max(max_end, i + nums[i]);
if (max_end >= length - 1) return true;
}
return false;
}
};
Jump Game II
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
主要注意点是最小次数，在某一次 max_end 内部发生的跳跃不会增加要跳跃的次数，因为这都在当前能到达
的 max_end 范围之内。
class Solution {
public:
int jump(vector<int>& nums) {
int cur_max_end = 0;
int next_max_end = 0;
int length = nums.size();
if (length < 2) return 0;
int count = 0;
for (int i = 0; i < length; ++i) {
// cout << "cur_max_end: " << cur_max_end << endl;
// cout << "next_max_end: " << next_max_end << endl;
if (cur_max_end == 0) {
cur_max_end = i + nums[i];
next_max_end = cur_max_end;
++count;
if (next_max_end >= length - 1) return count;
} else if (i <= cur_max_end) {
auto tmp = i + nums[i];
if (tmp > next_max_end) {
next_max_end = tmp;
} else {
continue;
}
} else {
++count;
cur_max_end = next_max_end;
next_max_end = max(next_max_end, i + nums[i]);
}
if (next_max_end >= length - 1) break;
}
return count + 1;
}
};
本文完