自助建站信息网,电子商务购物网站建设实验报告,公司网络系统维护,做盗版电影网站违法吗记忆化搜索 一、斐波那契数1、题目描述2、代码3、解析 二、不同路径1、题目描述2、代码3、解析 三、最长递增子序列1、题目描述2、代码3、解析 四、猜数字大小II1、题目描述2、代码3、解析 五、矩阵中的最长递增路径1、题目描述2、代码3、解析 一、斐波那契数
1、题目描述
le… 记忆化搜索 一、斐波那契数1、题目描述2、代码3、解析 二、不同路径1、题目描述2、代码3、解析 三、最长递增子序列1、题目描述2、代码3、解析 四、猜数字大小II1、题目描述2、代码3、解析 五、矩阵中的最长递增路径1、题目描述2、代码3、解析 一、斐波那契数
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:vectorvectorint memo;int uniquePaths(int m, int n) {memo vectorvectorint(m 1, vectorint(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) {vectorvectorint dp(m 1, vectorint(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(vectorint nums) {int n nums.size();vectorint 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, vectorint nums, vectorint 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(vectorint nums) {int n nums.size();vectorint 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:// 定义一个备忘录vectorvectorint memo;int getMoneyAmount(int n) {memo vectorvectorint(n 1, vectorint(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};vectorvectorint memo;int longestIncreasingPath(vectorvectorint matrix) {int ret 0;m matrix.size();n matrix[0].size();memo vectorvectorint(m, vectorint(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(vectorvectorint 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、解析
