classSolution {public:intjump(vector<int>& nums) {int n =nums.size(), step =0, start =0, end =0;while (end < n -1) { step++; int maxend = end +1;for (int i = start; i <= end; i++) {if (i +nums[i] >= n -1) return step; maxend =max(maxend, i +nums[i]); } start = end +1; end = maxend; }return step; }};
還有另一個寫起來更簡潔的做法:
classSolution {public:intjump(vector<int>& nums) {int jumps =0, curEnd =0, curFarthest =0;for (int i =0; i <nums.size() -1; i++) { curFarthest =max(curFarthest, i +nums[i]);if (i == curEnd) { jumps++; curEnd = curFarthest; } }return jumps; }};
解法三 - DP
首先定義一下 subproblem:
dp[i] = 到 index i 所需要的最少 jump 數
所以我們就知道 dp[i] = min(dp[前面所有可以到達 i 的 index]+1)。或是我們可以反過來說,我們看目前這個 index 可以到的範圍(start ~ end),然後就看 dp[end] 比較小(從其他地方跳到 end 所需 jump 數),還是 dp[start]+1 比較小(表示從 start 跳一步到達 end)。
classSolution {public:intjump(vector<int>& nums) { vector<int>dp(nums.size()); // Init with infinity, except the first index which should be 0 for (int i =1; i <nums.size(); i++) {dp[i] = numeric_limits<int>::max(); }for (int start =0; start <nums.size()-1; start++) {for (int end = start+1; end <= start+nums[start] && end<nums.size(); end++) {dp[end] =min(dp[end],dp[start] +1); } }returndp[nums.size() -1]; }};