題目：

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.

For example:
Given array A =?[2,3,1,1,4]

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. （Hard）

分析：

第一眼看完題目感覺用動態規劃肯定能解，但是感覺就是有很多重復計算在里面...因為題目只問了個最少步數。

果然寫出來之后華麗超時，但是代碼還是記錄一下吧

1 class Solution { 2 public: 3 int jump(vector<int>& nums) { 4 int dp[nums.size()]; 5 for (int i = 0; i < nums.size(); ++i) { 6 dp[i] = 0x7FFFFFFF; 7 } 8 dp[0] = 0; 9 for (int i = 1; i < nums.size(); ++i) { 10 for (int j = 0; j < i; ++j) { 11 if (j + nums[j] >= i) { 12 dp[i] = min(dp[i], dp[j] + 1); 13 } 14 } 15 } 16 return dp[nums.size() - 1]; 17 } 18 };

優化考慮類似BFS的想法，維護一個步數的范圍和一個能走到的最遠距離。

算法就是遍歷一遍數組，到每個位置的時候，更新他能到達的最遠距離end，如果一旦超過nums.size() - 1，就返回step + 1；

curEnd維護以當前步數能到達的最遠范圍，所以當i > curEnd時，step++，并且將curEnd更新為end。

代碼：

1 class Solution { 2 public: 3 int jump(vector<int>& nums) { 4 if (nums.size() == 1) { 5 return 0; 6 } 7 int step = 0, end = 0, curEnd = 0; 8 for (int i = 0; i < nums.size(); ++i) { 9 if (i > curEnd) { 10 step++; 11 curEnd = end; 12 } 13 end = max(end, nums[i] + i); 14 if (end >= nums.size() - 1) { 15 return step + 1; 16 } 17 } 18 return -1; 19 } 20 };

?

轉載于:https://www.cnblogs.com/wangxiaobao/p/5835856.html

總結

以上是生活随笔為你收集整理的LeetCode45 Jump Game II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。