記憶化搜索 vs 動態規劃

1. 記憶化搜索：有完全相同的問題/數據保存起來，帶有備忘錄的遞歸
2.記憶化搜索的步驟：
1、添加一個備忘錄 <可變參數，返回值>
2、遞歸每次返回的時候，將結果放入備忘錄中
3、在每次進入遞歸的時候，往備忘錄中查找一下
3. 記憶化搜索和常規的動態規劃都是動態規劃，暴搜 -> 記憶化搜索 -> 動態規劃
4. 有大量重復的問題才能改成記憶化搜索

斐波那契數

題目鏈接

題解

1. 創建一個備忘錄
2. 把備忘錄中的值初始化為斐波那契數中不可能出現的的值-1
3. 在每次遞歸完成之前，把值存入備忘錄中
4. 在每次進入遞歸的時候，查找一下備忘錄中是否有值，有值就直接返回，相當于剪枝

代碼

class Solution 
{
public:// 記憶化搜索int memo[31];int fib(int n) {memset(memo,-1,sizeof memo);return dfs(n);}int dfs(int n){if(memo[n] != -1){return memo[n];}if(n == 0 || n == 1){memo[n] = n;return n;}memo[n] = dfs(n-1) + dfs(n-2);return memo[n];}
};// 動態規劃
class Solution 
{
public:int dp[31];int fib(int n) {dp[0] = 0,dp[1] = 1;for(int i = 2;i <= n;i++){dp[i] = dp[i-1] + dp[i-2];}return dp[n];}
};

不同路徑

題目鏈接

題解

1. 函數頭的設計，只需要i和j的坐標
2. 返回條件：i == 0 || j == 0都是返回0
i == 1 && j == 1 第一個點返回1
3. 記憶化搜索就是創建一個二維的備忘錄，在遞歸之前往備忘錄中查找一下，返回之前把結果都存在備忘錄中

代碼

// 記憶化搜索
class Solution 
{
public:int memo[102][102];int uniquePaths(int m, int n) {return dfs(m,n);}int dfs(int m,int n){// 往備忘錄中查找一下if(memo[m][n]) return memo[m][n];   // 返回條件if(m == 0 || n == 0) return 0;// 第一個點if(m == 1 && n == 1){memo[m][n] = 1;return 1;} memo[m][n] = dfs(m-1,n) + dfs(m,n-1);return memo[m][n];}
};// 動態規劃
class Solution 
{
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m+1,vector<int>(n+1));dp[1][1] = 1;for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){if(i == 1 && j == 1) continue;dp[i][j] = dp[i-1][j] + dp[i][j-1];}}    return dp[m][n];}
};

最長遞增子序列

題目鏈接

題解

1. 記憶化搜索：每次枚舉以pos位置為起點的最長遞增子序列，讓pos+1位置的值和pos位置比較大小，如果大于就加一，函數頭需要nums和pos位置，函數體需要pos+1位置到n-1位置，dfs會完成找到最大遞增子序列的工作，+1是加上本身
2. 動態規劃：從后往前添加狀態，第一個循環用來枚舉位置，第二個循環用來比較大小，更新最長遞增子序列到dp[i]中，內層循環結束，更新一下最長的子序列，因為不知道哪個位置是最大的

代碼

 // 記憶化搜索
class Solution 
{
public:int memo[2510];int lengthOfLIS(vector<int>& nums) {int ret = 1;// 每次以i位置為起點往后搜索for(int i = 0;i < nums.size();i++){ret = max(dfs(nums,i),ret);}return ret;}int dfs(vector<int>& nums,int pos){if(memo[pos] != 0) return memo[pos];int ret = 1;for(int i = pos+1;i < nums.size();i++){if(nums[i] > nums[pos])ret = max(ret,dfs(nums,i)+1);}memo[pos] = ret;return memo[pos];}
};// 動態規劃
class Solution 
{
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();// 最短的子序列都是1vector<int> dp(n,1);int ret = 1;for(int i = n-1;i >= 0;i--){for(int j = i+1;j < n;j++){if(nums[j] > nums[i]){dp[i] = max(dp[i],dp[j] + 1);}}ret = max(ret,dp[i]);}    return ret;}
};

猜數字大小II

題目鏈接

題解

1. 暴搜 -> 記憶化搜索
2. 算法原理：在區間[1,n]固定一個點i，分為左右區間，尋找花費最小金錢達到必勝的方案，方案數是不止實例一那一種的，然后在左右枝中尋找所花費金額的最大值才能勝利
3. 函數頭需要傳參左右區間，函數體需要實現尋找多種方案中的最小花費和當前方案下的最大金錢，出現了重復的數據可以使用記憶化搜索

代碼

class Solution 
{
public:int memo[201][201];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,max(x,y) + head);}memo[left][right] = ret;return ret;}
};

矩陣中的最長遞增路徑

題目鏈接

題解

1. 算法原理：從一個點開始dfs，暴力枚舉出每一個遞增的路徑，返回其中最長的路徑即可
2. dfs函數的設計，需要i，j坐標去搜索每一個位置
3. 記憶化數組，如果出現相同的路徑，不用再次dfs，直接返回即可

代碼

class Solution 
{
public:int memo[201][201];int m,n;int longestIncreasingPath(vector<vector<int>>& matrix) {int ret = 1;m = matrix.size(),n = matrix[0].size();for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){ret = max(ret,dfs(matrix,i,j));}}return ret;}int dx[4] = {-1,1,0,0};int dy[4] = {0,0,-1,1};int dfs(vector<vector<int>>& matrix,int i,int j){if(memo[i][j]) return memo[i][j];int ret = 1;for(int k = 0;k < 4;k++){int x = dx[k] + i,y = dy[k] + j;if(x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]){ret = max(ret,dfs(matrix,x,y) + 1);}}memo[i][j] = ret;return ret;}
};

總結

1. 記憶化搜索就是先把暴力的dfs先寫出來，然后加一個備忘錄優化
2. 記憶化搜索也和常規的動態規劃是一樣的，即記憶化搜索也可以改為動態規劃的代碼
3. 出現大量重復的數據可以使用記憶化搜索，記憶化搜索可以使原本O(2^n)時間復雜度降為O(n)