?這種動規的方法時間復雜度是0（n2）

class Solution { public:bool canJump(vector<int>& nums) {int length = nums.size();bool can[length];for(int i = 1;i < length;i++)can[i] = false;can[0] = true;for(int i = 1;i < length;i++){for(int j = i-1;j >= 0;j--){if(can[j] == true && nums[j] >= i-j){can[i] = true;break;}}}return can[length-1];} };

?優化：記錄能到達的最遠距離，時間復雜度只有o（n）

class Solution { public:bool canJump(vector<int>& nums) {int length = nums.size();if(length < 0)return false;int canarrive = 0;for(int i = 0;i <= canarrive && canarrive < length-1;i++){if(i + nums[i] > canarrive)canarrive = i + nums[i];}return canarrive >= length-1;} };

?

轉載于:https://www.cnblogs.com/ymjyqsx/p/7468001.html

總結

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

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