四川创企科技有限责任公司,林云seo博客,湖州房产网,手机制作gif欢迎来到Cefler的博客#x1f601; #x1f54c;博客主页#xff1a;那个传说中的man的主页 #x1f3e0;个人专栏#xff1a;题目解析 #x1f30e;推荐文章#xff1a;【LeetCode】winter vacation training 前言 记忆化搜索是一种优化搜索算法的方法#xff0c;它可… 欢迎来到Cefler的博客 博客主页那个传说中的man的主页 个人专栏题目解析 推荐文章【LeetCode】winter vacation training 前言 记忆化搜索是一种优化搜索算法的方法它可以有效地减少重复计算和提高算法效率。该算法通过使用一个缓存数据结构来存储之前计算过的结果避免了重复计算相同的问题从而提高了搜索效率。
具体来说记忆化搜索通常使用递归算法实现。在每次递归调用时检查缓存中是否已经存储了当前问题的解。如果是则直接返回缓存中的结果否则计算当前问题的解并将其存储到缓存中然后返回结果。 目录 斐波那契数记忆化搜索与常规动态规划 不同路径最长递增子序列递归暴搜超出时间限制记忆化搜索优化递归时间 斐波那契数
原题链接斐波那契数
mycode:
class Solution {
public:int memory[101];//备忘录int dfs(int n){if(memory[n]!-1){return memory[n];}if(n2){memory[n] n;return n;}else{memory[n] fib(n-1)fib(n-2);return memory[n];}}int fib(int n) {memset(memory,-1,sizeof(memory));return dfs(n);}};记忆化搜索与常规动态规划 不同路径
原题链接不同路径
mycode:
class Solution {
public:int memo[101][101];//备忘录int dfs(int m,int n){if(memo[m][n]!0){return memo[m][n];}if(m0||n0) return 0;if(m1n1){memo[m][n] 1;return memo[m][n];}else{memo[m][n] dfs(m-1,n)dfs(m,n-1);return memo[m][n];}}int uniquePaths(int m, int n) {memset(memo,0,sizeof(memo));return dfs(m,n);}
};最长递增子序列
原题链接最长递增子序列
递归暴搜超出时间限制
mycode:
class Solution {
public:int dfs(vectorint nums,int pos){int ret 1;for(int i pos1;inums.size();i){if(nums[i]nums[pos]){ret max(dfs(nums,i)1,ret);}}return ret;}int lengthOfLIS(vectorint nums) {int ret 0;for(int i 0;inums.size();i){ret max(ret,dfs(nums,i));}return ret;}
};记忆化搜索优化递归时间
class Solution {
public:int dfs(vectorint nums,int pos,vectorint memo){if(memo[pos]!0) return memo[pos];int ret 1;for(int i pos1;inums.size();i){if(nums[i]nums[pos]){ret max(dfs(nums,i,memo)1,ret);}}memo[pos] ret;return ret;}int lengthOfLIS(vectorint nums) {int ret 0;vectorint memo(nums.size());//备忘录for(int i 0;inums.size();i){ret max(ret,dfs(nums,i,memo));}return ret;}
