day57--动态规划15

这篇具有很好参考价值的文章主要介绍了day57--动态规划15。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

  •  392.判断子序列 
  •  115.不同的子序列  

第一题:判断子序列

给定字符串 s 和 t ,判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。

示例 1:

  • 输入:s = "abc", t = "ahbgdc"
  • 输出:true

1、动态规划五部曲

(1)确定dp数组以及下标的含义

dp[i][j]表示以下标i-1为结尾的字符串s,和下标j-1为结尾的字符串t,相同子序列的长度为dp[i][j]

(2)确定递推公式

if(s[i-1]==t[j-1]) 

t中找到了一个字符在s中也出现了

if(s[i-1]!=t[j-1])

相当于当前对应元素不相同,t需要删除元素,跳到下一个元素进行匹配

if(s[i-1]==t[j-1]) 那么dp[i][j]=dp[i-1][j-1] +1;  在上一次满足条件的长度情况下加1

if(s[i-1]!=t[j-1])  此时t要删除元素,t如果把当前元素t[j-1]删除,那么dp[i][j]的数值就是看s[i-1]和t[j-2]的比较结果,即dp[i][j]=dp[i][j-1]

(3)dp数组如何初始化

 dp[i][0]肯定是没有匹配成功的值,所以为0

同理,dp[0][j]也为0

(4)确定遍历顺序

dp[i][j]依赖于dp[i-1][j-1]和dp[i][j-1],所以从前到后遍历,先遍历s数组,然后遍历t数组

(5)举例推导

day57--动态规划15,动态规划,服务器,算法

第二题:不同的子序列

给定一个字符串 s 和一个字符串 t ,计算在 s 的子序列中 t 出现的个数。

字符串的一个 子序列 是指,通过删除一些(也可以不删除)字符且不干扰剩余字符相对位置所组成的新字符串。(例如,"ACE" 是 "ABCDE" 的一个子序列,而 "AEC" 不是)

题目数据保证答案符合 32 位带符号整数范围。

0、问题是问在字符串s中有多少种取出字符串t的方法

动态规划五部曲:

(1)确定dp数组以及下标的含义

dp[i][j]:以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]

(2)确定递推公式

s[i-1]与t[j-1]相等

s[i-1]与t[j-1]不相等

情况一:dp[i][j]=dp[i-1][j-1]+dp[i-1][j]

情况二:dp[i][j]=dp[i-1][j]  ,也就是等于以i-2为结尾的s子序列中出现j-1为结尾的t序列的个数

(3)dp数组初始化

dp[i][0]和dp[0][j]需要进行初始化

dp[i][0] 表示:以i-1为结尾的s可以随便删除元素,出现空字符串的个数。

那么dp[i][0]一定都是1,因为也就是把以i-1为结尾的s,删除所有元素,出现空字符串的个数就是1。

再来看dp[0][j],dp[0][j]:空字符串s可以随便删除元素,出现以j-1为结尾的字符串t的个数。

那么dp[0][j]一定都是0,s如论如何也变成不了t。

最后就要看一个特殊位置了,即:dp[0][0] 应该是多少。

dp[0][0]应该是1,空字符串s,可以删除0个元素,变成空字符串t。

(4)确定遍历顺序

dp[i][j]=dp[i-1][j-1]+dp[i-1][j]或者dp[i][j]=dp[i-1][j]都是根据左上方和右上方推导出来

外层遍历s数组,内层遍历t数组

(5)举例推导

day57--动态规划15,动态规划,服务器,算法文章来源地址https://www.toymoban.com/news/detail-737044.html

int numDistinct(string s, string t) {
        vector<vector<uint64_t>> dp(s.size()+1,vector<uint64_t> (t.size()+1));
        for(int i=0;i<s.size();i++) dp[i][0]=1;
        for(int j=1;j<t.size();j++) dp[0][j]=0;
        for(int i=1;i<=s.size();i++){
            for(int j=1;j<=t.size();j++){
                if(s[i-1]==t[j-1]){
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                }
                else {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[s.size()][t.size()];


    }

到了这里,关于day57--动态规划15的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法|Day40 动态规划9

    LeetCode 198- 打家劫舍 题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 题目描述 :你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统, 如果两间相邻的房屋在同一晚上

    2024年02月12日
    浏览(31)
  • 算法|Day46 动态规划14

    LeetCode 1143- 最长公共子序列 题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 题目描述 :给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串:它是由原

    2024年02月11日
    浏览(46)
  • 算法记录 | Day53 动态规划

    思路: 本题和动态规划:718. 最长重复子数组 (opens new window)区别在于这里不要求是连续的了,但要有相对顺序,即:“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。 1.确定dp数组(dp table)以及下标的含义 dp[i][j] :长度为[0, i - 1]的字符串text1与长度为[0,

    2024年02月03日
    浏览(50)
  • 算法记录 | Day46 动态规划

    思路: 1.确定dp数组以及下标的含义 dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词 。 2.确定递推公式 如果 s[0: j] 可以拆分为单词(即 dp[j] == True ),并且字符串 s[j: i] 出现在字典中,则 dp[i] = True 。 如果 s[0: j] 不可以拆分为单词(即

    2024年02月02日
    浏览(39)
  • 算法记录 | Day38 动态规划

    对于动态规划问题,将拆解为如下五步曲 确定dp数组(dp table)以及下标的含义 确定递推公式 dp数组如何初始化 确定遍历顺序 举例推导dp数组 思路: 确定dp数组(dp table)以及下标的含义:dp[i]的定义为:第i个数的斐波那契数值是dp[i] 确定递推公式:状态转移方程 dp[i] = dp

    2023年04月22日
    浏览(44)
  • 算法记录 | Day55 动态规划

    思路: 1.确定dp数组(dp table)以及下标的含义: dp[i][j] 表示以下标i-1为结尾的字符串s,和以下标j-1为结尾的字符串t,相同子序列的长度为 dp[i][j] 。 2.确定递推公式: if (s[i - 1] == t[j - 1]) t中找到了一个字符在s中也出现了, dp[i][j] = dp[i - 1][j - 1] + 1 if (s[i - 1] != t[j - 1]) 相当于t要

    2024年02月03日
    浏览(49)
  • 算法记录 | Day45 动态规划

    改为:一步一个台阶,两个台阶,三个台阶,…,直到 m个台阶。问有多少种不同的方法可以爬到楼顶呢? 1阶,2阶,… m阶就是物品,楼顶就是背包。 每一阶可以重复使用,例如跳了1阶,还可以继续跳1阶。 问跳到楼顶有几种方法其实就是问装满背包有几种方法。 此时大家

    2024年02月11日
    浏览(33)
  • 【算法|动态规划No.15】leetcode1035. 不相交的线

    个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望对大家有所帮助 🍓希望我们一起努力、成长,共同进步。

    2024年02月06日
    浏览(44)
  • Day 42算法记录| 动态规划 08

    单词就是物品,字符串s就是背包 1.dp[0]背包啥也不要用装,true。 2. for循环,顺序很重要,所以先背包再物品 如果求组合数就是外层for循环遍历物品,内层for遍历背包 。 如果求排列数就是外层for遍历背包,内层for循环遍历物品 。 3.递归: 要么装包或者不装 添加链接描述 把

    2024年02月15日
    浏览(31)
  • 算法day39|动态规划:不同路径Ⅰ、Ⅱ

    https://leetcode.cn/problems/unique-paths/ 了解下标含义——这里是行列数 理解为什么dfs不能做这道题(超时) https://leetcode.cn/problems/unique-paths-ii/ 初始化时也应该注意限制条件 注意特殊情况的判断

    2024年02月06日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包