柚子快報邀請碼778899分享：算法 遞歸 記憶化搜索專題篇
柚子快報邀請碼778899分享：算法 遞歸 記憶化搜索專題篇
目錄
斐波那契數(shù)
不同路徑
最長遞增子序列
猜數(shù)字大小II
矩陣中的最長遞增路徑
聲明：下面將主要使用遞歸+記憶化搜索來解決問題?。?！
斐波那契數(shù)
題目
思路
斐波那契數(shù)的特點就是除了第一個數(shù)是0，第二個數(shù)是1，其余的數(shù)都是前兩個數(shù)的和。
顯然我們很容易用遞歸實現(xiàn)，但是會超時的，因為計算第n個位置的斐波那契數(shù)的大小時，會重復很多次的計算某些位置的斐波那契數(shù)，因此如果我們能記錄下已經(jīng)計算過的位置對應的斐波那契數(shù)時，當再次需要該位置的斐波那契數(shù)時，就不用再重復的進行計算了。
代碼
class Solution {
long long memo[101];
public:
int fib(int n) {
memset(memo,-1,sizeof memo);
// std::fill(memo, memo + 101, -1);
return dfs(n);
}
int dfs(int n){
if(memo[n]!=-1)
return memo[n];
if(n==0 || n==1){
memo[n]=n;
return memo[n];
}
memo[n]=(dfs(n-1)+dfs(n-2))%1000000007;
return memo[n];
}
};
class Solution {
// public:
// int fib(int n) {
// if(n==0 || n==1)
// return n;
// vector
// dp[0]=0,dp[1]=1;
// for(int i=2;i<=n;i++)
// dp[i]=(dp[i-1]+dp[i-2])%1000000007;
// return dp[n];
// }
// };
不同路徑
題目
思路
本道題很容易使用遞歸實現(xiàn)，但是會超時，原因同上一道題一樣，會大量重復的計算一些以某些位置為起點到終點的路徑數(shù)，而且時間復雜度是呈指數(shù)級別的，因此，我們可以和上一道題一樣，如果將已經(jīng)計算過的以某些位置為起點到終點的路徑數(shù)記錄下來，當再次求以這些位置為起點到終點的路徑數(shù)時，直接使用即可，避免了大量的重復計算。
代碼
class Solution {
public:
int uniquePaths(int m, int n) {
vector
return dfs(m,n,memo);
}
int dfs(int x,int y,vector
if(memo[x][y]!=0) return memo[x][y];
if(x==0|| y==0) return 0;
if(x==1 && y==1){
memo[x][y]=1;
return 1;
}
else{
memo[x][y]=dfs(x-1,y,memo)+dfs(x,y-1,memo);
return memo[x][y];
}
}
};
class Solution {
public:
int uniquePaths(int m, int n) {
vector
// dp[0][1]=1;
dp[1][0]=1;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
dp[i][j]=dp[i-1][j]+dp[i][j-1];
}
}
return dp[m][n];
}
};
最長遞增子序列
題目
思路
這道題已經(jīng)在之前的博客中寫過了，之前使用的是動態(tài)規(guī)劃和貪心+二分，之前的動態(tài)規(guī)劃是從前往后分析的，下面將使用遞歸+記憶化搜素，以及從后往前的分析的動態(tài)規(guī)劃。
遞歸+記憶化搜素
從頭到尾掃描數(shù)組，分別計算以該位置為起點的最長遞增子序列的長度，并把每次計算好的結果進行記錄，當下次再次用到以已記錄位置為起點的最長遞增子序列的長度時，直接拿已經(jīng)計算好的結果即可，避免了不少重復的計算。
從后往前的分析的動態(tài)規(guī)劃
可以說是在分析前面的遞歸+記憶化搜素方法的基礎上摸索出來的，如何定義狀態(tài)表示和狀態(tài)轉移方程等，這里不再贅述，可以參考之前的博客。
代碼
class Solution {
public:
int lengthOfLIS(vector
//記憶化搜索
int ret=1;
vector
for(int i=0;i ret=max(ret,dfs(i,nums,memo)); return ret; } int dfs(int pos,vector if(memo[pos]!=0) return memo[pos]; int k=1; for(int i=pos+1;i if(nums[i]>nums[pos]) k=max(k,dfs(i,nums,memo)+1); memo[pos]=k; return k; } };//遞歸+記憶化搜素 class Solution { public: int lengthOfLIS(vector int n=nums.size(); vector for(int i=n-1;i>=0;i--) for(int j=i+1;j if(nums[i] dp[i]=max(dp[i],dp[j]+1); } return *max_element(dp.begin(),dp.end()); } };//動態(tài)規(guī)劃 猜數(shù)字大小II 題目 思路 上面之所以沒有截示例，是因為示例比較長，而且文字描述很多，比較容易看暈，下面也是采用遞歸+記憶化搜素來解決，因為如果只使用遞歸會超時，因為會大量的重復計算相同位置的值，如果能夠?qū)⒚看斡嬎愫玫闹当４嫫饋?，下次使用時直接取，就能夠較少大量的操作，更佳。 從頭到尾掃描整個數(shù)組，分別計算以該位置為起點的最大花費，然后計算所有起始位置的最大花費的最小值。 代碼 class Solution { int memo[201][201]; public: int getMoneyAmount(int n) { return dfs(1,n); } int dfs(int left,int right){ if(left>=right) return 0; if(memo[left][right]!=0) return memo[left][right]; int ret=INT_MAX; for(int head=left;head<=right;head++){ int x=dfs(left,head-1); int y=dfs(head+1,right); ret=min(ret,head+max(x,y)); } memo[left][right]=ret; return ret; } }; 矩陣中的最長遞增路徑 題目 思路 下面也是采用遞歸+記憶化搜素來解決，因為如果只使用遞歸會超時，因為會大量重復計算以某位置為起點的最長遞增路徑，如果能夠記錄下以某位置為起點的最長遞增路徑，當下次使用時直接取即可，就能夠減少大量的重復計算，以示例1為例，比如就以【2】【1】位置的1為起始位置，計算時會有一條向上到6的路徑，但是如果已經(jīng)計算過以這個6為起始位置的最長遞增路徑的長度，可以直接使用，就不用再重復計算了。 代碼 class Solution { public: int n,m; int maxlen[201][201]; int dx[4]={0,0,1,-1}; int dy[4]={1,-1,0,0}; int longestIncreasingPath(vector int ret=0; n=matrix.size(),m=matrix[0].size(); for(int i=0;i for(int j=0;j ret=max(ret,dfs(matrix,i,j)); return ret; } int dfs(vector if(maxlen[i][j]!=0) return maxlen[i][j]; int ret=1; for(int k=0;k<4;k++){ int x=i+dx[k]; int y=j+dy[k]; if(x>=0 && x ret=max(ret,dfs(matrix,x,y)+1); } maxlen[i][j]=ret; return ret; } }; 柚子快報邀請碼778899分享：算法 遞歸 記憶化搜索專題篇 好文鏈接
本文內(nèi)容根據(jù)網(wǎng)絡資料整理，出于傳遞更多信息之目的，不代表金鑰匙跨境贊同其觀點和立場。
轉載請注明，如有侵權，聯(lián)系刪除。
Zoodmall動物樂園
