---

一、斐波那契數

1、題目描述

leetcode鏈接

2、代碼

常規遞歸暴搜代碼：

class Solution
{
public:int fib(int n){if(n == 0) return 0;if(n == 1) return 1;return fib(n - 1) + fib(n - 2);}
};

備忘錄版：

class Solution 
{
public:// 備忘錄int memo[31];int fib(int n) {memset(memo, -1, sizeof(memo)); // 先將備忘錄進行初始化為-1，因為-1根本就不會遇到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:// dp表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];    }
};

3、解析

二、不同路徑

1、題目描述

leetcode鏈接

2、代碼

記憶化搜索：

class Solution 
{
public:vector<vector<int>> memo;int uniquePaths(int m, int n) {memo = vector<vector<int>>(m + 1, vector<int>(n + 1));return dfs(m, n);}int dfs(int i, int j){if(memo[i][j] != 0){return memo[i][j];}if(i == 0 || j == 0){return 0; // 越界情況}if(i == 1 && j == 1){memo[i][j] = 1;return 1;}memo[i][j] = dfs(i - 1, j) + dfs(i, j - 1);return memo[i][j];}
};

動態規劃：

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];}
};

3、解析

三、最長遞增子序列

1、題目描述

leetcode鏈接

2、代碼

記憶化搜索：

class Solution 
{
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> memo(n); // 定義一個備忘錄int ret = 0;for(int i = 0; i < n; i++){ret = max(ret, dfs(i, nums, memo)); // 相信dfs一定能處理好往后進行遍歷}return ret;}int dfs(int pos, vector<int>& nums, vector<int>& memo){if(memo[pos] != 0) // 此處是已經使用過了{return memo[pos];}int ret = 1; // 必須從1開始，不然一直是0比較，會出現邊界情況for(int i = pos + 1; i < nums.size(); i++){if(nums[i] > nums[pos])ret = max(ret, dfs(i, nums, memo) + 1);}memo[pos] = ret; // 保存一下return memo[pos];}
};

動態規劃做法：

class Solution 
{
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();vector<int> dp(n, 1); // 定義一個有n個數為1的dp數組int ret = 0;// 從后往前遍歷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;}
};

3、解析

四、猜數字大小II

1、題目描述

leetcode鏈接

2、代碼

class Solution 
{
public:// 定義一個備忘錄vector<vector<int>> memo;int getMoneyAmount(int n) {memo = vector<vector<int>>(n + 1, vector<int>(n + 1));// 暴搜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;}
};

3、解析

五、矩陣中的最長遞增路徑

1、題目描述

leetcode鏈接

2、代碼

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

3、解析