目錄

斐波那契數(shù)

不同路徑

最長遞增子序列

猜數(shù)字大小II

矩陣中的最長遞增路徑

---

聲明：下面將主要使用遞歸+記憶化搜索來解決問題！！！

斐波那契數(shù)

題目

思路

斐波那契數(shù)的特點就是除了第一個數(shù)是0，第二個數(shù)是1，其余的數(shù)都是前兩個數(shù)的和。

顯然我們很容易用遞歸實現(xiàn)，但是會超時的，因為計算第n個位置的斐波那契數(shù)的大小時，會重復(fù)很多次的計算某些位置的斐波那契數(shù)，因此如果我們能記錄下已經(jīng)計算過的位置對應(yīng)的斐波那契數(shù)時，當(dāng)再次需要該位置的斐波那契數(shù)時，就不用再重復(fù)的進(jìn)行計算了。

代碼

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<int> dp(n+1);
//         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)，但是會超時，原因同上一道題一樣，會大量重復(fù)的計算一些以某些位置為起點到終點的路徑數(shù)，而且時間復(fù)雜度是呈指數(shù)級別的，因此，我們可以和上一道題一樣，如果將已經(jīng)計算過的以某些位置為起點到終點的路徑數(shù)記錄下來，當(dāng)再次求以這些位置為起點到終點的路徑數(shù)時，直接使用即可，避免了大量的重復(fù)計算。

代碼

class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> memo(m+1,vector<int>(n+1));return dfs(m,n,memo);}int dfs(int x,int y,vector<vector<int>>& memo){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<vector<int>> dp(m+1,vector<int>(n+1));// 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ù)組，分別計算以該位置為起點的最長遞增子序列的長度，并把每次計算好的結(jié)果進(jìn)行記錄，當(dāng)下次再次用到以已記錄位置為起點的最長遞增子序列的長度時，直接拿已經(jīng)計算好的結(jié)果即可，避免了不少重復(fù)的計算。

從后往前的分析的動態(tài)規(guī)劃

可以說是在分析前面的遞歸+記憶化搜素方法的基礎(chǔ)上摸索出來的，如何定義狀態(tài)表示和狀態(tài)轉(zhuǎn)移方程等，這里不再贅述，可以參考之前的博客。

代碼

class Solution {
public:int lengthOfLIS(vector<int>& nums) {//記憶化搜索int ret=1;vector<int> memo(nums.size());for(int i=0;i<nums.size();i++)ret=max(ret,dfs(i,nums,memo));return ret;}int dfs(int pos,vector<int>& nums,vector<int>& memo){if(memo[pos]!=0) return memo[pos];int k=1;for(int i=pos+1;i<nums.size();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>& nums) {int n=nums.size();vector<int> dp(n,1);for(int i=n-1;i>=0;i--)for(int j=i+1;j<n;j++){if(nums[i]<nums[j])dp[i]=max(dp[i],dp[j]+1);}return *max_element(dp.begin(),dp.end());}
};//動態(tài)規(guī)劃

猜數(shù)字大小II

題目

思路

上面之所以沒有截示例，是因為示例比較長，而且文字描述很多，比較容易看暈，下面也是采用遞歸+記憶化搜素來解決，因為如果只使用遞歸會超時，因為會大量的重復(fù)計算相同位置的值，如果能夠?qū)⒚看斡嬎愫玫闹当４嫫饋?#xff0c;下次使用時直接取，就能夠較少大量的操作，更佳。

從頭到尾掃描整個數(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;}
};

矩陣中的最長遞增路徑

題目

思路

下面也是采用遞歸+記憶化搜素來解決，因為如果只使用遞歸會超時，因為會大量重復(fù)計算以某位置為起點的最長遞增路徑，如果能夠記錄下以某位置為起點的最長遞增路徑，當(dāng)下次使用時直接取即可，就能夠減少大量的重復(fù)計算，以示例1為例，比如就以【2】【1】位置的1為起始位置，計算時會有一條向上到6的路徑，但是如果已經(jīng)計算過以這個6為起始位置的最長遞增路徑的長度，可以直接使用，就不用再重復(fù)計算了。

代碼

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<vector<int>>& matrix) {int ret=0;n=matrix.size(),m=matrix[0].size();for(int i=0;i<n;i++)for(int j=0;j<m;j++)ret=max(ret,dfs(matrix,i,j));return ret;}int dfs(vector<vector<int>>& matrix,int i,int j){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<n && y>=0 && y<m && matrix[x][y]>matrix[i][j])ret=max(ret,dfs(matrix,x,y)+1);}maxlen[i][j]=ret;return ret;}
};