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

网站数据搬家宁波网络推广方法

网站数据搬家,宁波网络推广方法,wordpress未验证邮箱用户,企业咨询诊断报告目录 一、什么是动态规划? 二、动态规划的使用步骤 1.状态表示 2.状态转移方程 3.初始化 4.填表顺序 5.返回值 三、试题讲解 1.最小花费爬楼梯 2.下降路径最小和 3.解码方法 一、什么是动态规划? 动态规划(Dynamic Programming&…

目录

一、什么是动态规划?

二、动态规划的使用步骤

1.状态表示

2.状态转移方程

3.初始化

4.填表顺序

5.返回值

三、试题讲解

1.最小花费爬楼梯

2.下降路径最小和

3.解码方法


一、什么是动态规划?

        动态规划(Dynamic Programming,简称dp)是一种通过将复杂问题分解为更小的子问题来解决的算法思想,尤其适用于具有重叠子问题最优子结构的优化问题。其核心目标是避免重复计算,通过存储中间结果(记忆化)来提升效率。

动态规划 vs 分治法

  • 共同点:都将问题分解为子问题。

  • 区别

    • 分治法(如归并排序)的子问题独立,无重叠,无需存储中间结果。

    • 动态规划的子问题有重叠,需存储中间结果避免重复计算。

二、动态规划的使用步骤

        为了方便理解下面我将从感性的角度来给大家讲解动态规划的使用步骤

1.状态表示

        首先在解决问题的时候我们通常会使用一块空间来记录已处理的数据,我们把这块空间叫作dp表。

        当我们在解决一个小问题时需要借助之前已解决的问题的数据,就可以到dp表里面查,当前这个小问题解决后继续把它相关的信息存到dp表,然后继续解决下一个小问题。

        这个dp表中的一小块数据表示什么?这些问题指的就是状态表示。在用动态规划解决问题时,要面对最重要的问题就是dp表的状态应该表示是什么?

在解决这个问题时我们通常都是从这几个角度去思考:

  • 1.经验+题目要求
  • 2.分析问题的过程中,发现重复子问题。
  • 3.当我们发现子问题后,假设前(或后)几个小问题已经解决,思考我们在解决当前问题时有没有需要前面已解决的问题的什么信息?

2.状态转移方程

        dp[i]等于什么?这就是状态转移方程。它通常要依赖于已经计算过的状态。

3.初始化

在创建好dp表后主要任务就是对dp表的填写,初始化dp表的作用有以下两点:

  1. 保证填表的时候不越界。
  2. 保证填表的正确性。

4.填表顺序

        为使填写当前状态的时候,所需要的状态已经计算过了。

5.返回值

        最后结合题目要求和状态表示计算结果并返回。

三、试题讲解

1.最小花费爬楼梯

        首先我们分析题目,我们的起点是0或1的位置,而终点是n位置(注意不是n-1位置)。我们在爬楼梯时支付一次费用可以爬一个或两个台阶。

        当我们尝试从动态规划方向去解决,那么我们试着去构造一下相同的子问题,并且假设它已经解决。

注:为了方便在下文我都会把动态规划简称为“动规” 

        用动规解题过程中,在找子问题时我总结了一个很厉害的小技巧,就是保留主问题的逻辑,而换一个问题的对象。比如这里,主问题是起点爬到楼顶的最小花费,那么构造子问题时我们只需要保留这个问题的逻辑,而把楼顶这个对象改成任意位置i。那么我们就得到了一个子问题(即从起点爬到i位置的最小花费)。然后我们再假设前面的相同的子问题已经解决。

比如:

        动规题复杂多变,以上技巧可以解决大部分的基础动规题,但更多的只是作为一个小经验,并不是所有动规题都可以通过构建子问题来解决的。

        在解一个题时,状态表示可以是很多,不同的状态表示就决定了不同的状态转移方程,而要判断一个状态表示是否正确只需看是否能根据该状态表示推出正确的状态转移方程。

能够理解上图那么动态规划的五步骤就水到渠成了。

  • 状态表示: dp[i]:表示爬到i时的最小花费
  • 状态转移方程: dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2])
  • 初始化: dp表初始化为全0
  • 填表顺序: 从下标为2的位置开始,并且从左往右填写
  • 返回值: return dp[n]

代码示例:

class Solution {
public:int minCostClimbingStairs(vector<int>& cost){int n=cost.size();vector<int> dp(n+1);//默认值就是0,不用初始化for(int i=2;i<=n;i++) dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);return dp[n];    }
};

        除了刚才的状态表示我们还可以换一个,只需要改变一下子问题,同样的技巧,主问题逻辑不变,把起点这个对象改成任意位置i, 那么我们就得到了一个子问题(即从i位置爬到楼顶的最小花费)。

  • 状态表示: dp[i]:表示从i爬到楼顶的最小花费
  • 状态转移方程: dp[i]=cost[i]+min(dp[i+1],dp[i+2])
  • 初始化: dp[n-1]=cost[n-1],dp[n-2]=cost[n-2]
  • 填表顺序: 从右往左
  • 返回值: return min(dp[0], dp[1])

        我们可以发现状态表示的改变使得其他四个步骤的实现逻辑改变,所以可见状态表示的重要性。

代码示例:

class Solution {
public:int minCostClimbingStairs(vector<int>& cost){int n=cost.size();vector<int> dp(n);dp[n-1]=cost[n-1],dp[n-2]=cost[n-2];for(int i=n-3;i>=0;i--) dp[i]=cost[i]+min(dp[i+1],dp[i+2]);return min(dp[0],dp[1]);    }
};

        提示:空间优化:在我们填写某一个状态的时候只需要使用它的前两个状态,所以可以把dp数组简化为两个变量就可以解决问题(需要注意变量的更新)。通常把该优化方法叫做滚动数组”。很多基础动规都可以进行这样的优化,大家可以试着去实现,这一点在后面也不再提。 

        提示:为了减少逻辑上的赘述,在以下题解中我都只会讲解一种状态表示作为示例。 

2.下降路径最小和

通过上一题找子问题的经验,我们可以这样做:

抓住主问题:从第一行任意位置下降到最后一行的任意一个位置的最小和。 

        保留问题的主逻辑,把对象“第一行任意位置”或“最后一行任意位置”更改,比如更改“最后一行任意位置”为“第i行的任意位置j”。得到子问题,即从“第一行任意位置下降到第i行的任意位置j的最小和”

        接下来假设与它相同的子问题都解决,并利用它们的结果。如下:

动规五步骤:

  • 状态表示: dp[i][j]:从第一行任意位置下降到第i行j列的最小和
  • 状态转移方程: dp[i][j]=matrix[i][j]+min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]) )
  • 初始化:越界区域如下:

        

        创建(n+1)*(n+2)的dp表初始化为全INT_MAX(这样创建dp表减少了为防止越界而做特殊判断带来的成本),再将第一行初始化为全0把dp表初始化为全INT_MAX,是为了防止越界区域参与最小值的筛选再把第一行初始化为全0是逻辑需要,总的目的都是为了保证填表的正确性。

  • 填表顺序: 从上到下,从左往右(或从右往左,只要能保证在填写当前状态时需要的状态已计算过即可)
  • 返回值: 返回最后一行的最小值

代码示例: 

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix){int n=matrix.size();//题目明确指出是方形,所以行数和列数都一样。vector<vector<int>> dp(n+1,vector<int>(n+2,INT_MAX));for(int j=0;j<n+2;j++) dp[0][j]=0;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dp[i][j]=matrix[i-1][j-1]+min(min(dp[i-1][j-1],dp[i-1][j]),dp[i-1][j+1]);int ret=INT_MAX;for(int j=1;j<=n;j++) ret=min(ret,dp[n][j]);return ret;}
};

3.解码方法

        主问题: 一个非空字符s的解码方法的总数。但我们好像无法从中获取到可以更改的对象,再回去观察上面我们解决的两道问题。它们主问题的逻辑中都是带有区间式的,比如第一题:从起点到终点,第二题:从第一行到最后一行。那么如果我们还想要那个找子问题的技巧去确定状态表示,那么在总结主问题时就要朝着带有区间式的方向去想。

        这里我们可以把主问题总结为:从s字符串的下标0开始到下标n-1结束的解码方法总数。那么这样我们就构造出了一个区间“开始”——“结束”。子问题就好构建得多了。

子问题:从下标0开始到下标i结束的解码方法总数。

  • 状态表示: dp[i]:表示从下标0开始到下标i结束的解码方法总数
  • 状态转移方程:

        解决了状态表示但这个题的难点主要在于状态转移方程。

     

         我们可以把单独解码和前一个联合解码分开讨论。如果单独解码成功相当于在i-1的所有解码方法中统一加上一个s[i],所以为dp[i-1],解码失败的话,说明不能单独解码,所以结果为0

        同理联合解码成功相当于在i-2的所有解码方法中统一加上一个s[i]与s[i-1]的复合,所以为dp[i-2],解码失败的话,说明不能联合解码所以结果为0最后只需要把单独解码与联合解码的结果相加。

  • 初始化: 因为我们在用dp[i]时需要用到dp[i-1]和dp[i-2]的状态,所以最好把dp[0]和dp[1]初始化。dp[0]可以这样写dp[0]=s[i]!='0',但dp[1]的初始化会比较麻烦,它的初始化逻辑和上面的状态转移方程是一样的。而在下面填表时同样要用到这样的逻辑,就会显得很累赘。

        我们可以使用这样一个初始化技巧:

        那么可以做一个n+1大小的dp表,然后错开一位表示,即 dp[i]:表示从下标0开始到下标i-1结束的解码方法总数。为保证后面的填表顺序正确我们需要dp[1]=s[i]!='0',这是必然的。而dp[0]该初始化为什么?我们可以思考什么时候用到dp[0],即s[0]与s[1]解码成功时,那么它必然是dp[0]=1

  • 填表顺序:从dp的2下标开始,并从左往右。
  • 返回值: return dp[n]

代码示例:

class Solution {
public:int numDecodings(string s){vector<int> dp(s.size()+1,0);dp[1]=s[0]!='0',dp[0]=1;for(int i=2;i<dp.size();i++){int m=(s[i-2]-'0')*10+s[i-1]-'0';if(s[i-1]!='0') dp[i]+=dp[i-1];if(m>=10&&m<=26) dp[i]+=dp[i-2];}return dp.back();}
};

非常感谢您能耐心读完这篇文章。倘若您从中有所收获,还望多多支持呀!74c0781738354c71be3d62e05688fecc.png

http://www.zhongyajixie.com/news/17068.html

相关文章:

  • 上海网站建设备案号谷歌seo综合查询
  • 动态网站开发实例网上书店长沙正规关键词优化价格从优
  • 建网站的外包公司个人网站免费域名注册
  • 浙江网站建设电话广州网站优化步骤
  • 天津网站建设价位便宜的seo网络营销推广
  • 抖音代运营有什么内容优化推广联盟
  • 明星用什么软件做视频网站怎么免费注册域名
  • 自建网站国家审核要多久百度新闻客户端
  • 手表商城网站建设外贸网站建设优化
  • 东莞网站推广模板产品推广计划书怎么写
  • 网站建设专家论证会专业网站优化培训
  • 廊坊网站排名优化公司热词分析工具
  • 海口市龙华区核酸检测优化方法
  • 贵州省建设项目验收备案网站模板建站平台
  • 贵州建设厅安全员b证考试网站谷歌搜索引擎大全
  • 做外贸通常用哪些网站新乡网站优化公司
  • 哪个网站有手机网络推广的方法和技巧
  • 编程 给别人做网站网站备案查询官网
  • 徐老师在那个网站做发视频下载海外seo推广公司
  • 重庆綦江网站制作公司哪家专业win7优化设置
  • 淮北矿业 集团 工程建设有限责任公司网站简述seo和sem的区别
  • 汽车品牌推广策划方案seo综合查询怎么关闭
  • 淘宝联盟怎么自己做网站推广域名查询网址
  • 谷歌 网站做推广优化seo深圳
  • 精品网站建设费用网站的seo 如何优化
  • 单位网站制作费用报价单大数据培训课程
  • 网站建设 广西杭州网站优化效果
  • 什么网站可以申请做汉语老师网站目录提交
  • 最后的目的是什么sem优化
  • 郑州网站设计培训html简单网页代码