這是leetcode上的一道題。拿到這道題最容易想到是回溯算法，即遞歸從第一個元素開始跳，跳到某個元素之后在當(dāng)前的位置上繼續(xù)跳，如果不滿足條件就回溯。之前一直不知道回溯的過程，今天可算是弄明白了。簡單來說就是一個人站在十字路口選擇了一條路走向目的地，而在這條路上可能還有十字路口，還得做選擇，選擇了一條接下去結(jié)果走不通（代表迭代完畢）返回最近的十字路口，選擇另一條路走，走到頭之后再返回最近的十字路口選擇另一條，如此的迭代，當(dāng)最近的十字路口的路（四個方向）都走完之后，返回上上一個十字路口。再找另外一條。如此的重復(fù)下去直到第一個十字路口的四個方向都選擇完為止。回溯有很多種應(yīng)用，比如二叉樹的遍歷。在一開始學(xué)習(xí)遞歸的時候自己一遇到這樣形式的就不知道程序如何運(yùn)行了 ，糾結(jié)程序是運(yùn)行完第一個遞歸直接進(jìn)入第二個遞歸還是一直運(yùn)行第一個遞歸直到不滿足條件后在運(yùn)行第二條，當(dāng)時由于自己不知道回溯這種東西，錯以為運(yùn)行一次遞歸后就直接運(yùn)行第二條遞歸。其實(shí)是一直運(yùn)行第一條遞歸直到不滿足條件為止。然后回到當(dāng)前節(jié)點(diǎn)的父結(jié)點(diǎn)去遍歷右子樹，如果右子樹也為空，再往上返回一層遍歷祖父結(jié)點(diǎn)的右子樹。如此的循環(huán)。我這是比較抽象的說明，如果想看二叉樹的具體遍歷可以去看這篇博客

https://blog.csdn.net/I_love_blog/article/details/66971598
? ? ?

PreOrderTraverse(T->lchild);//遞歸左子樹 PreOrderTraverse(T->rchild);//遞歸右子樹

這道題的解法C++代碼

class Solution { public:bool canJump(vector<int>& nums) {return tmp(0,nums);}bool tmp(int curr,vector<int> &nums){int j=nums.size()-1;if(curr==j)return true;int cnt=min(curr+nums[curr],j);for(int n=curr+1;n<=cnt;n++){if(tmp(n,nums))return true;}return false;} };

在leetcode上提交后顯示超時。我們可以看下這道題的算法復(fù)雜度有O（2^n）在其中會有很多的重復(fù)運(yùn)算，比如tmp（2）就要計算很多次，如果我們能用一個數(shù)組去保存這些元素的結(jié)果就會省去很多時間，雖然需要一定的空間，但是速度有很大的提高還是值得的，其實(shí)動態(tài)規(guī)劃就是典型的空間換時間的思想。

class Solution { public:bool canJump(vector<int>& nums) {vector<int>dp(nums.size());//定義一個數(shù)組來存放元素是否可以遍歷到最后dp[nums.size()-1]=1;//最后一個數(shù)一定可以到達(dá)自己跳自己return tmp(dp,0,nums);}bool tmp(vector<int>&dp,int curr,vector<int> &nums){if(dp[curr])return dp[curr]==1?true:false;int j=nums.size()-1;//if(curr==j)//return true;int cnt=min(curr+nums[curr],j);for(int n=curr+1;n<=cnt;n++){if(tmp(dp,n,nums)){dp[n]=1;//1代表該數(shù)據(jù)可以跳到最后return true;}}dp[curr]=-1;//-1代表該數(shù)據(jù)不可以跳到最后return false;} };

?通過dp來存放元素是否可以遍歷到最后，在leetcode上提交不再顯示超時。省時間的原因我們可以拿一個例子來說明，比如說第二個行不通的例子，我們可以發(fā)現(xiàn)無論從 3、2、1開始跳都會跳到0這個位置，而0這個位置是跳不到最后的。我們又發(fā)現(xiàn)無論從3開始跳還是從2、1開始都會跳到0這個位置，如果沒有dp存放結(jié)果3、2、1跳的時候每次都要計算這個位置可不可以。我們存放了這個結(jié)果是false之后，無論哪個數(shù)跳到這都直接返回false省去了很多計算。但是我們發(fā)現(xiàn)這個算法中還是有很多冗余，我們只需要數(shù)組中的一個元素跳到最后就ok了，沒有必要遍歷整個數(shù)組。算法代碼如下

class Solution { public:bool canJump(vector<int>& nums) { int k = 0;for (int i = 0; i < nums.size(); i++){if (i > k) return false;k = max(k, i + nums[i]);}return true;} };

?

總結(jié)

以上是生活随笔為你收集整理的一道题教会你回溯、动态规划、贪心的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。