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

广州电子商务网站建设 v天津seo排名公司

广州电子商务网站建设 v,天津seo排名公司,设计师工作室,做网站网页需要多久动态规划_leetcode 647. 回文子串 516.最长回文子序列今天是动态规划最后一天的题了,整个过程已经接近尾声了! 647. 回文子串 确定dp数组(dp table)以及下标的含义 本题如果我们定义,dp[i] 为 下标i结尾的字符串有 dp…

动态规划_leetcode 647. 回文子串 516.最长回文子序列

今天是动态规划最后一天的题了,整个过程已经接近尾声了!

647. 回文子串

请添加图片描述

  • 确定dp数组(dp table)以及下标的含义
    本题如果我们定义,dp[i] 为 下标i结尾的字符串有 dp[i]个回文串的话,我们会发现很难找到递归关系。
    dp[i] 和 dp[i-1] ,dp[i + 1] 看上去都没啥关系。
    在判断字符串S是否是回文,那么如果知道 s[1],s[2],s[3] 这个子串是回文的,那么只需要比较 s[0]和s[4]这两个元素是否相同,如果相同的话,这个字符串s 就是回文串。
    那么此时是不是能找到一种递归关系,也就是判断一个子字符串(字符串的下表范围[i,j])是否回文,依赖于,子字符串(下表范围[i + 1, j - 1])) 是否是回文。
    所以为了明确这种递归关系,dp数组是要定义成一位二维dp数组。
    布尔类型的dp[i][j]:表示区间范围[i,j] (注意是左闭右闭)的子串是否是回文子串,如果是dp[i][j]为true,否则为false。

  • 确定递推公式
    整体上是两种,就是s[i]与s[j]相等,s[i]与s[j]不相等这两种。

    • 当s[i]与s[j]不相等,那没啥好说的了,dp[i][j]一定是false。
    • 当s[i]与s[j]相等时,这就复杂一些了,有如下三种情况
      • 情况一:下标i 与 j相同,同一个字符例如a,当然是回文子串
      • 情况二:下标i 与 j相差为1,例如aa,也是回文子串
      • 情况三:下标:i 与 j相差大于1的时候,例如cabac,此时s[i]与s[j]已经相同了,我们看i到j区间是不是回文子串就看aba是不是回文就可以了,那么aba的区间就是 i+1 与 j-1区间,这个区间是不是回文就看dp[i + 1][j - 1]是否为true。
if s[i] == s[j]if j - i <= 1:result += 1dp[i][j] = Trueelif dp[i + 1][j - 1]:result += 1dp[i][j] = True
  • dp数组如何初始化
    dp[i][j]可以初始化为true么? 当然不行,怎能刚开始就全都匹配上了。
    所以dp[i][j]初始化为false。

  • 确定遍历顺序
    首先从递推公式中可以看出,情况三是根据dp[i + 1][j - 1]是否为true,在对dp[i][j]进行赋值true的。
    dp[i + 1][j - 1] 在 dp[i][j]的左下角,如图:
    请添加图片描述
    所以一定要从下到上,从左到右遍历,这样保证dp[i + 1][j - 1]都是经过计算的。

  • 举例推导dp数组
    请添加图片描述

class Solution:def countSubstrings(self, s: str) -> int:dp = [[False] * len(s) for _ in range(len(s))]result = 0for i in range(len(s)-1, -1, -1): #注意遍历顺序for j in range(i, len(s)):if s[i] == s[j]:if j - i <= 1: #情况一 和 情况二result += 1dp[i][j] = Trueelif dp[i+1][j-1]: #情况三result += 1dp[i][j] = Truereturn result

516.最长回文子序列
516.最长回文子序列

  • 确定dp数组(dp table)以及下标的含义
    dp[i][j]:字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
  • 确定递推公式
    • 在判断回文子串的题目中,关键逻辑就是看s[i]与s[j]是否相同。
      如果s[i]与s[j]相同,那么dp[i][j] = dp[i + 1][j - 1] + 2;
    • 如果s[i]与s[j]不相同,说明s[i]和s[j]的同时加入 并不能增加[i,j]区间回文子序列的长度,那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
      加入s[j]的回文子序列长度为dp[i + 1][j]。
      加入s[i]的回文子序列长度为dp[i][j - 1]。
      那么dp[i][j]一定是取最大的,即:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
  • dp数组如何初始化
    首先要考虑当i 和j 相同的情况,从递推公式:dp[i][j] = dp[i + 1][j - 1] + 2; 可以看出 递推公式是计算不到 i 和j相同时候的情况。
    所以需要手动初始化一下,当i与j相同,那么dp[i][j]一定是等于1的,即:一个字符的回文子序列长度就是1。
    其他情况dp[i][j]初始为0就行,这样递推公式:dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); 中dp[i][j]才不会被初始值覆盖。
  • 确定遍历顺序
    从递归公式中,可以看出,dp[i][j] 依赖于 dp[i + 1][j - 1] ,dp[i + 1][j] 和 dp[i][j - 1],如图:
    请添加图片描述
    所以遍历i的时候一定要从下到上遍历,这样才能保证下一行的数据是经过计算的。
    j的话,可以正常从左向右遍历。
  • 举例推导dp数组
    请添加图片描述
class Solution:def longestPalindromeSubseq(self, s: str) -> int:dp = [[0 for _ in range(len(s))] for _ in range(len(s))]for i in range(len(s)):dp[i][i] = 1for i in range(len(s)-1,-1,-1):for j in range(i+1,len(s)):if s[i] == s[j]:dp[i][j] = dp[i+1][j-1] +2else:dp[i][j] = max(dp[i][j-1], dp[i+1][j])return dp[0][-1]

今天这两道题还挺绕的,第一题数组定义不能再根据以往经验来以最后一个字符为限,另外遍历顺序也有所不同!

http://www.15wanjia.com/news/21146.html

相关文章:

  • 网站用社交图标做链接侵权吗百度竞价排名案例分析
  • 如何做品牌网站网络优化的意义
  • 做二手房又做网站的朋友圈推广平台
  • 做淘宝客需要那先网站网络营销软件站
  • 编程app下载优化方法
  • 新疆建设云微信小程序优化服务平台
  • 在国内做电商网站需要什么审核搜索推广
  • 中小企业网站推广淘宝客推广一天80单
  • 上海网站备案电商运营方案计划书
  • 做网站横幅用什么软件好老王搜索引擎入口
  • 百度网页入口官网优化网站内容的方法
  • 海南建设工程信息网站网络工程师是干什么的
  • 广西壮族自治区行政执法人员培训seo外链建设的方法
  • 2021年免费的网站有哪些财经新闻最新消息
  • 运营网站赚钱手机网页链接制作
  • 图片网站收录什么叫关键词举例
  • 推荐一个可以做ppt的网站推广软件平台
  • 华为云定制建站服务怎么样科学新概念seo外链
  • 万州微网站建设关键词搜索点击软件
  • 萍乡网站制作公司友情链接价格
  • 我和丝袜做的视频网站怎样创建网页
  • wordpress跳转站点怎样优化关键词到首页
  • 安庆网站开发百家号seo怎么做
  • 巴彦淖尔 网站建设公司运营策划营销
  • web创建一个简单的查询网站在线生成网站
  • 要建网站怎么做百度sem
  • 欧美在路边给了钱就可以做网站seo案例分享
  • 有哪些做家教网站免费涨1000粉丝网站
  • 深圳网站设计很棒 乐云践新百度在西安有分公司吗
  • 山东免费网站建设网络营销策划书格式