数据结构与算法 -- 子序列问题

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

一、子序列问题

        子数组问题是连续的,而子序列问题是不连续的。比如说字符串 “I wanna keep a giraffe in my backyard” 的一种子序列就可以是 “Igbackd”。 子序列不再要求答案是一个连续的串。一个字符串的子序列,是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。举个例子,“ace” 是 “abcde” 的子序列,但是 “aec” 就不是 “abcde” 的子序列。

二、最长回文子序列

1、问题描述

问题:给定一个字符串 s ,找到其中最长的回文子序列,并返回该序列的长度。可以假设 s 的最大长度为 1000。 


示例1:

输入:"asssasms"
输出:5
解释:一个可能的最长回文子序列为 "sssss",另一种可能的答案是 "asssa"。

2、算法分析

1)初始化状态

        单个字符一定是它自己的回文;

2)状态参数

        一个是起始位置,另一个是结束位置。在算法的执行过程中,起始和结束位置是变化的,因此它们是状态参数。 

3)决策

        当前子问题的答案就是通过前面的子问题 ➕ 当前的决策推导出来的。当前的决策就是:计算出向子问题的两边分别扩充一个元素后得到的答案。 

4)备忘录

        DP[i][j],其对应的值是字符串 i…j 中最长回文子序列的长度。 

3、状态方程

子序列,数据结构与算法,算法,动态规划,数据结构

4、算法实现文章来源地址https://www.toymoban.com/news/detail-701984.html

package main

import "fmt"


func DP(str string, length int) int {
	byteSlice := []byte(str)

	// 创建备忘录
	dp := make([][]int, length)
	for i := range dp{
		dp[i] = make([]int, length)
	}

	// 初始化状态
	for i := 0; i < length; i++ {
		dp[i][i] = 1
	}

	// 转移方程转换实现
	for i := length - 1; i >= 0; i-- {
		for j := i+1; j < length; j++ {
			if byteSlice[i] == byteSlice[j] {
				dp[i][j] = 2 + dp[i+1][j-1];
			} else {
				if dp[i+1][j] > dp[i][j-1] {
					dp[i][j] = dp[i+1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
			}
		}
	}
	return dp[0][length-1] // 输出答案
}

func main() {
	str := "asssasms"
	length := len(str)
	fmt.Println(DP(str, length))  // 输出答案
}

三、最长公共子序列

1、问题描述

问题:给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。若这两个字符串没有公共子序列,则返回 0。

其中:

1 ≤ text1.length ≤ 1000;

1 ≤ text2.length ≤ 1000;

输入的字符串只含有小写英文字符。 


示例1:

输入:text1 = "abcde", text2 = "ade" 
输出:3  
解释:最长公共子序列是 "ade",它的长度为 3。

2、算法分析

1)初始化状态

        当两个字符的其中一个为空串,或同时为空串时,原问题的答案肯定是 0。显然,一个字符串与空串的公共子序列肯定是空的。 

2)状态参数

        用变量 i 和变量 j 描述了整个问题的求解空间,备忘录是基于二维数组构建的。因此,我们的状态参数就是变量 i 和变量 j。 

3)决策

对于 text1 和 text2 这两个字符串中的每个字符 text1[i] 和 text2[j],其实只有两种选择:

1、text1[i−1]==text2[j−1],即当前遍历的两个字符在最长公共子序列中,此时 DP[i][j]=1+DP[i−1][j−1];

2、text1[i−1]!=text2[j−1],即当前遍历的两个字符至少有一个不在最长公共子序列中。仿照最长回文子序列的处理方法,由于两个字符至少有一个不在,因此我们需要丢弃一个。因此在不等的情况下,需要进一步作出决策。 

由于我们要求的是最长公共子序列,因此哪个子问题的答案比较长,就留下谁:max(DP[i−1][j], DP[i][j−1])。

4)备忘录

        DP[i][j] 表示的是 text1[0…i] 和 text2[0…j] 的最长公共子序列的长度。 

3、状态方程

子序列,数据结构与算法,算法,动态规划,数据结构

4、算法实现

package main

import "fmt"


func DP(str1 string, str2 string) int {
	byteSlice1 := []byte(str1)
	byteSlice2 := []byte(str2)

	length1 := len(str1)
	length2 := len(str2)

	// 创建备忘录
	dp := make([][]int, length1+1)
	for i := range dp{
		dp[i] = make([]int, length2+1)
	}

	// 初始化状态
	for i := 0; i < length1+1; i++ {
		for j := 0; j  < length2+1; j++ {
			dp[i][j] = 0
		}
	}

	// 转移方程转换实现
	for i := 1; i<= length1; i++ {
		for j := 1; j <= length2; j++ {
			if byteSlice1[i-1] == byteSlice2[j-1] {
				dp[i][j] = 1 + dp[i-1][j-1];
			} else {
				if dp[i-1][j] > dp[i][j-1] {
					dp[i][j] = dp[i-1][j]
				} else {
					dp[i][j] = dp[i][j-1]
				}
			}
		}
	}
	return dp[length1][length2] // 输出答案
}

func main() {
	str1 := "abcde"
	str2 := "ade"
	fmt.Println(DP(str1, str2))  // 输出答案
}

声明:本文参考极客时间《动态规划面试宝典》 

到了这里,关于数据结构与算法 -- 子序列问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构与算法之美学习笔记:40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?

    本节课程思维导图: 淘宝的“双十一”购物节有各种促销活动,比如“满 200 元减 50 元”。假设你女朋友的购物车中有 n 个(n100)想买的商品,她希望从里面选几个,在凑够满减条件的前提下,让选出来的商品价格总和最大程度地接近满减条件(200 元),这样就可以极大限

    2024年02月03日
    浏览(52)
  • 数据结构与算法之美学习笔记:41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题

    本节课程思维导图: 今天,我主要讲动态规划的一些理论知识。学完这节内容,可以帮你解决这样几个问题:什么样的问题可以用动态规划解决?解决动态规划问题的一般思考过程是什么样的?贪心、分治、回溯、动态规划这四种算法思想又有什么区别和联系? 什么样的问

    2024年02月02日
    浏览(66)
  • 数据结构与算法-动态规划

    (我猜是做的多了背的题多了就自然懂了) 迭代法一般没有通用去重方式,因为已经相当于递归去重后了 这两个问题其实是一个问题,一般直接写出的没有去重的递归法,复杂度很高,此时需要使用备忘录去重,而备忘录去重时间复杂度和使用dp数组进行迭代求解时间复杂度相同

    2024年02月04日
    浏览(46)
  • 数据结构与算法之贪心&动态规划

            一:思考         1.某天早上公司领导找你解决一个问题,明天公司有N个同等级的会议需要使用同一个会议室,现在给你这个N个会议的开始和结束 时间,你怎么样安排才能使会议室最大利用?即安排最多场次的会议?电影的话 那肯定是最多加票价最高的,入场

    2024年02月09日
    浏览(47)
  • python算法与数据结构---动态规划

    记不住过去的人,注定要重蹈覆辙。 对于一个模型为n的问题,将其分解为k个规模较小的子问题(阶段),按顺序求解子问题,前一子问题的解,为后一子问题提供有用的信息。在求解任一子问题时,通过决策求得局部最优解,依次解决各子问题。最后通过简单的判断,得到

    2024年02月20日
    浏览(76)
  • 数据结构与算法 | 动态规划算法(Dynamic Programming)

    上一篇文末已经提到了记忆化搜索是动态规划(Dynamic Programming)的一种形式,是一种自顶向下(Top-Down)的思考方式,通常采用递归的编码形式;既然动态规划有自顶向下(Top-Down)的递归形式,自然想到对应的另外一种思考方式 自底向上( Bottom-Up ) ,也就是本篇要写的内

    2024年02月05日
    浏览(46)
  • Java数据结构与算法----动态规划(背包篇)

    1.1.算法思路 0/1背包是动态规划、背包问题中最经典的问题啦!它主要的问题是: 给定n种物品、这n种物品的重量分别是,价值分别是 ,而你有一个容量为C的背包,请问如何求出所能拿的最大价值呢? 对于动态规划,我们先需要找到一条推导公式,然后确定边界: 我们设

    2024年02月07日
    浏览(50)
  • 数据结构与算法:动态规划(Dynamic Programming)详解

    动态规划(Dynamic Programming,简称DP) 是一种在数学、管理科学、计算机科学、经济学和生物信息学等领域中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划经常被用于求解优化问题。 动态规划的核心思想是将复杂问题分解为更小的子问

    2024年04月25日
    浏览(48)
  • 数据结构与算法 -- 子序列问题

    一、子序列问题         子数组问题是连续的,而子序列问题是不连续的。比如说字符串 “I wanna keep a giraffe in my backyard” 的一种子序列就可以是 “Igbackd”。 子序列不再要求答案是一个连续的串。一个字符串的子序列,是由原字符串在不改变字符的相对顺序的情况下删

    2024年02月09日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包