当前位置: 首页 > news >正文

天津网站排名优化外贸营销网站制作

天津网站排名优化,外贸营销网站制作,logo艺术字转换器,网站设计一般会遇到哪些问题文章目录 记忆化搜索 vs 动态规划斐波那契数题解代码 不同路径题解代码 最长递增子序列题解代码 猜数字大小II题解代码 矩阵中的最长递增路径题解代码 总结 记忆化搜索 vs 动态规划 1. 记忆化搜索:有完全相同的问题/数据保存起来,带有备忘录的递归 2.记忆…

文章目录

  • 记忆化搜索 vs 动态规划
  • 斐波那契数
    • 题解
    • 代码
  • 不同路径
    • 题解
    • 代码
  • 最长递增子序列
    • 题解
    • 代码
  • 猜数字大小II
    • 题解
    • 代码
  • 矩阵中的最长递增路径
    • 题解
    • 代码
  • 总结

记忆化搜索 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)

http://www.cadmedia.cn/news/7012.html

相关文章:

  • 网站建设网页设计培训班怎么制作网站教程步骤
  • 自己想做个网站需要多少钱优化网站seo公司
  • 芜湖网站建设推广公司搜索引擎优化是什么?
  • seo做论坛和企业网站差别百度自动点击器怎么用
  • 宁波网站推广运营公司网上推销产品的软件
  • 给我一个网站电工培训内容
  • 广州建网站开发seo型企业网站seo排名优化软件有用吗
  • 旅行社网站规划与建设如何在网上做销售推广
  • 系统开发工具有哪些长沙seo优化价格
  • 淘客推广佣金广安seo外包
  • 网站开发遇到的难题解决seo优化排名工具
  • 江西专业的网站建设制作sem和seo是什么
  • 专业做红木家具网站网络推广员是干什么的
  • wordpress 大战深圳优化服务
  • 广州新建站百度客户端下载
  • 怎么建设医疗美容网站百度推广开户多少钱一个月
  • 做网站的公司哪家强百度seo如何做
  • 车都建设投资集团网站关键词优化排名平台
  • 有关风水的网站建设栏目线上营销的优势
  • 互动网页设计北京seo运营推广
  • web网站开发意义百度文库厦门网络推广哪家强
  • 阿里巴巴建网站软文案例大全300字
  • 网络网站建设办公seo搜索引擎优化工具
  • 网站免费在线客服系统营销推广方式有哪些
  • 九江建设公司网站数据统计网站有哪些
  • 广州公司网站制作招聘信息网站目录
  • 电子商务网站建设的首要问题新闻稿营销
  • 内蒙网站建设seo优化什么叫做seo
  • 德州王霞网站建设阿里域名注册网站
  • 佛山网站推广怎么做站内搜索引擎