【代码随想录——动态规划——序列问题】

1.最初上升子序列

在这里插入图片描述

func lengthOfLIS(nums []int) int {
    length := len(nums)
    dp := make([]int, length)
    for i:=0;i<length;i++{
        dp[i] = 1
    }
    //对于每一个i，我们都需要回过头去遍历是否可以更新长度
    for i:=0;i<length;i++{
        for j:=0;j<i;j++{
            if nums[i]>nums[j]{
                dp[i] = max(dp[i],dp[j]+1)
            }
        }
    }
    maxLen := 0
    for i:=0;i<length;i++{
        if maxLen<dp[i]{
            maxLen = dp[i]
        }
    }
    return maxLen
}

2.最长连续递增序列

在这里插入图片描述

func findLengthOfLCIS(nums []int) int {
    length := len(nums)
    // 初始化
    dp := make([]int,length)
    for i:=0;i<length;i++{
        dp[i] = 1
    }
    // 递推
    for i:=1;i<length;i++{
        if nums[i]>nums[i-1]{
            dp[i] = dp[i-1]+1
        }
    }
    // 查找最大值
    maxLen := 0 
    for i:=0;i<length;i++{
        if maxLen<dp[i]{
            maxLen = dp[i]
        }
    }
    return maxLen
}

3.最长重复子数组


这道题目的初始化比较有趣，需要进行一定的注意。

func findLength(nums1 []int, nums2 []int) int {
	len1 := len(nums1)
	len2 := len(nums2)
	dp := make([][]int, len1)
	for i := 0; i < len1; i++ {
		dp[i] = make([]int, len2)
	}
	maxLen := 0
	// 初始化
	for i := 0; i < len2; i++ {
		if nums1[0] == nums2[i] {
			dp[0][i] = 1
		}
		if dp[0][i] > maxLen {
			maxLen = dp[0][i]
		}
	}
	for i := 0; i < len1; i++ {
		if nums2[0] == nums1[i] {
			dp[i][0] = 1
		}
		if dp[i][0] > maxLen {
			maxLen = dp[i][0]
		}
	}
	//递推
	for i := 1; i < len1; i++ {
		for j := 1; j < len2; j++ {
			if nums1[i] == nums2[j] {
				dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1)
				if dp[i][j] > maxLen {
					maxLen = dp[i][j]
				}
			}
		}
	}
	return maxLen
}

4.最长公共子序列

在这里插入图片描述

func longestCommonSubsequence(text1 string, text2 string) int {
    len1 := len(text1)
    len2 := len(text2)
    dp := make([][]int,len1+1)
    for i:=0;i<=len1;i++{
        dp[i] = make([]int,len2+1)
    }
    //初始化
    //开始递归
    for i:=1;i<=len1;i++{
        for j:=1;j<=len2;j++{
            if text1[i-1]==text2[j-1]{
                dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1)
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
            }
        }
    }
    return dp[len1][len2]
}

5.不相交的线

实际上与上题”最长公共子序列“完全相同

func maxUncrossedLines(nums1 []int, nums2 []int) int {
    len1 := len(nums1)
    len2 := len(nums2)
    dp := make([][]int,len1+1)
    for i:=0;i<=len1;i++{
        dp[i] = make([]int,len2+1)
    }
    for i:=1;i<=len1;i++{
        for j:=1;j<=len2;j++{
            if nums1[i-1]==nums2[j-1]{
                dp[i][j] = max(dp[i][j],dp[i-1][j-1]+1)
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1])
            }
        }
    }
    return dp[len1][len2]
}

6.最大子序和

在这里插入图片描述

6.1 贪心

func maxSubArray(nums []int) int {
    max := nums[0]
    count := 0

    for i := 0; i < len(nums); i++{
        count += nums[i]
        if count > max{
            max = count
        }
        if count < 0 {
            count = 0
        }
    } 
    return max
}

6.2 动态规划

func maxSubArray(nums []int) int {
    //创建dp数组
    //dp数组中i的含义为以nums[i]结尾的最大连续子数组和
    dp := make([]int,len(nums))
    //dp数组初始化
    dp[0]=nums[0]
    //递推
    for i:=1;i<len(nums);i++{
        dp[i] = max(dp[i-1]+nums[i],nums[i])
    }
    //寻找最大
    ans := dp[0]
    for i:=0;i<len(nums);i++{
        if dp[i]>ans{
            ans = dp[i]
        }
    }
    return ans
}

7.判断子序列

在这里插入图片描述

7.1 非动态规划

func isSubsequence(s string, t string) bool {
    if len(s)==0 {
        return true
    }
    if len(s)>len(t){
        return false
    }
    index := 0
    for i:=0;i<len(t);i++{
        if s[index]==t[i]{
            index++
            if index==len(s){
                return true
            }
        }
    }
    return false
}

7.2 动态规划

func isSubsequence(s string, t string) bool {
    if len(s)==0 {
        return true
    }
    if len(s)>len(t){
        return false
    }
    len1 := len(s)
    len2 := len(t)
    dp := make([][]int,len1+1)
    for i:=0;i<=len1;i++{
        dp[i] = make([]int,len2+1)
    }
    for i:=1;i<=len1;i++{
        for j:=1;j<=len2;j++{
            if s[i-1]==t[j-1]{
                dp[i][j] = dp[i-1][j-1]+1
            }else{
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    return dp[len1][len2]==len1
}

8.不同的子序列

在这里插入图片描述

func numDistinct(s string, t string) int {
    dp:= make([][]int,len(s)+1)
    //dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
    for i:=0;i<len(dp);i++{
        dp[i] = make([]int,len(t)+1)
    }
    // 初始化
    for i:=0;i<len(dp);i++{
    	//[i][0]即空字符出现的个数，只能全部删除，所以都为1
        dp[i][0] = 1
    }
    // dp[0][j] 为 0，默认值，因此不需要初始化
    for i:=1;i<len(dp);i++{
        for j:=1;j<len(dp[i]);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[len(dp)-1][len(dp[0])-1]
}

9.两个字符串的删除操作

在这里插入图片描述

func minDistance(word1 string, word2 string) int {
	//dp[i][j]表示word1[:i-1]和word[:j-1]中相同的子序列长度
	dp := make([][]int,len(word1)+1)
	for i:=0;i<=len(word1);i++{
		dp[i] = make([]int,len(word2)+1)
	}
	//初始化
    for i:=0;i<=len(word1);i++{
        dp[i][0] = i
    }
    for j:=0;j<=len(word2);j++{
        dp[0][j] = j
    }
    //递推
	for i:=1;i<=len(word1);i++{
		for j:=1;j<=len(word2);j++{
			if word1[i-1]==word2[j-1]{
				dp[i][j] = dp[i-1][j-1]
			}else{
				dp[i][j] = min(dp[i-1][j-1]+2,dp[i-1][j]+1,dp[i][j-1]+1)
			}
		}
	}
	return dp[len(word1)][len(word2)]
}

10.编辑距离

在这里插入图片描述

func minDistance(word1 string, word2 string) int {
    //dp[i][j]代表以下标i-1为结尾的字符串word1，和以下标j-1为结尾的字符串word2，最近编辑距离为dp[i][j]
    dp := make([][]int, len(word1)+1)
    for i:=0;i<=len(word1);i++{
        dp[i] = make([]int,len(word2)+1)
    }
    //dp数组初始化
    for i:=0;i<=len(word1);i++{
        dp[i][0] = i
    }
    for j:=0;j<=len(word2);j++{
        dp[0][j] = j
    }
    //dp数组推导
    for i:=1;i<=len(word1);i++{
        for j:=1;j<=len(word2);j++{
            if word1[i-1]==word2[j-1]{
                dp[i][j] = dp[i-1][j-1]
            }else{
                dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
            }
        }
    }
    return dp[len(word1)][len(word2)]
}

11.回文子串

在这里插入图片描述

func countSubstrings(s string) int {
    //dp创建
    dp := make([][]bool,len(s))
    for i:=0;i<len(s);i++{
        dp[i]=make([]bool,len(s))
    }
    result := 0
    //递推
    for i:=len(s)-1;i>=0;i--{
        for j:=i;j<len(s);j++{
            if s[i]==s[j]{
                if j-i<=1{
                    result += 1
                    dp[i][j]=true
                }else if dp[i+1][j-1]{
                    result += 1
                    dp[i][j]=true
                }
            }
        }
    }
    return result
}

12.最长回文子序列

在这里插入图片描述

func longestPalindromeSubseq(s string) int {
    //创建dp数组,dp[i][j]表示[i:j]中最长的回文子序列的长度
    dp := make([][]int,len(s))
    for i:=0;i<len(s);i++{
        dp[i] = make([]int,len(s))
        dp[i][i] = 1
    }
    //dp数组递推
    for i:=len(s)-1;i>=0;i--{
        for j:=i+1;j<len(s);j++{
            if s[i] == s[j] {
				dp[i][j] = dp[i+1][j-1] + 2
			} else {
				dp[i][j] = max(dp[i][j-1], dp[i+1][j])
			}
        }
    }
    return dp[0][len(s)-1]
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/745129.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

聊聊AI在企业数字化转型中的作用

聊聊AI在企业数字化转型中的作用

随着科技的飞速发展&#xff0c;人工智能&#xff08;AI&#xff09;已经深入到我们生活的方方面面&#xff0c;尤其在数字化转型的浪潮中&#xff0c;AI技术更是扮演着举足轻重的角色。数字化转型&#xff0c;简而言之&#xff0c;就是企业利用数字技术来改造其业务运营方式&a…
阅读更多...
SpringBoot学习03-[Spring Boot与Web开发]

SpringBoot学习03-[Spring Boot与Web开发]

Spring Boot与Web开发 RestTemplateMockMvc在SPringBoot中使用 SpringBoot整合swagger2SpringBoot的springmvc自动配置底层原理包含ContentNegotiatingViewResolver和BeanNameViewResolverContentNegotiatingViewResolverBeanNameViewResolver 支持提供静态资源&#xff0c;包括…
阅读更多...
【面试干货】Java中==和equals()的区别

【面试干货】Java中==和equals()的区别

【面试干货】Java中和equals&#xff08;&#xff09;的区别 1、操作符2、equals()方法3、总结 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收藏不迷路&#x1f496; 在Java中&#xff0c;和equals()是两个常用的比较操作符和方法&#xff0c;但它们之间的用法和…
阅读更多...
聚星文社官网

聚星文社官网

推文工具可以帮助你将小说内容简洁明了地转化为推文形式&#xff0c;以便更好地在社交媒体上进行宣传和推广。以下是一些建议的小说推文工具&#xff1a; 聚星文社 字数统计工具&#xff1a;使用字数统计工具&#xff0c;如Microsoft Word或在线字数统计器&#xff0c;来确保你…
阅读更多...
PCM、WAV，立体声，单声道，正弦波等音频素材

PCM、WAV，立体声，单声道，正弦波等音频素材

1&#xff09;PCM、WAV音频素材&#xff0c;分享给将要学习或者正在学习audio开发的同学。 2&#xff09;内容属于原创&#xff0c;若转载&#xff0c;请说明出处。 3&#xff09;提供相关问题有偿答疑和支持。 常用的Audio PCM WAV不同采样率&#xff0c;不同采样深度&#…
阅读更多...
【结构体】详解

【结构体】详解

Hi~&#xff01;这里是奋斗的小羊&#xff0c;很荣幸您能阅读我的文章&#xff0c;诚请评论指点&#xff0c;欢迎欢迎 ~~ &#x1f4a5;&#x1f4a5;个人主页&#xff1a;奋斗的小羊 &#x1f4a5;&#x1f4a5;所属专栏&#xff1a;C语言 &#x1f680;本系列文章为个人学习…
阅读更多...
web前端大作业--美团外卖1

web前端大作业--美团外卖1

文章目录 概述代码截图代码链接 概述 web美团 登录和注册功能、页面展示。 代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title><link rel"stylesheet" href&quo…
阅读更多...
大模型技术的应用场景

大模型技术的应用场景

大模型技术&#xff08;Large Language Model&#xff0c;LLM&#xff09;是指具有大量参数和训练数据的神经网络模型&#xff0c;它能够学习语言的统计规律&#xff0c;并生成与人类书写的文本相似的文本。大模型技术在近年来取得了重大进展&#xff0c;并开始在各种领域得到应…
阅读更多...
中国杀出全球首个烹饪大模型

中国杀出全球首个烹饪大模型

什么&#xff1f;烹饪也有大模型&#xff1f;&#xff01; 没有听错&#xff0c;这就是国产厨电龙头老板电器最新发布——“食神”大模型。 数十亿级行业数据&#xff0c;数千万级知识图谱加持&#xff0c;据称还是全球首个。 它能为每个人提供个性化量身定制的解决方案&…
阅读更多...
从入口文件搭建php项目

从入口文件搭建php项目

入口文件index.php <?phprequire CallBack.php; // 处理回调请求逻辑 $bot new CallBack();// 请求方式 if (isset($_GET[method])) {$method $_GET[method];if (method_exists($bot, $method)) {return $bot->$method();} else {echo "没有该功能";die();…
阅读更多...
系统思考—啤酒游戏经营决策沙盘

系统思考—啤酒游戏经营决策沙盘

在日常的教学中&#xff0c;我们通过系统思考仿真演练深入探索决策背后的动因。例如&#xff0c;我经常教授的麻省理工学院研发的“啤酒游戏”和“人民航空策略模拟”&#xff0c;这些都是麻省理工MBA学生的必修课。此外&#xff0c;还有更简洁的“红黑游戏”“收获季节”等模拟…
阅读更多...
Typora 更换皮肤

Typora 更换皮肤

typora 下载激活 上面的链接已经讲了如何下载激活typora工具,本篇说一下如何给typora换肤 typora 中文官网 进入官网,在整体界面布局的上方找到主题 下面以其中一个主题为例,跟换主题皮肤 下载该主题 找到旁边的release 下拉窗体,在Assets里面找这种压缩包,通过名字很容易区…
阅读更多...
无限制数字（仅仅int类型）的大小的自然排序算法

无限制数字（仅仅int类型）的大小的自然排序算法

直接上代码&#xff1a; #include <iostream> #include <vector> #include <string> #include <algorithm> #include <cctype>// Function to compare two strings in a natural way bool naturalCompare(const std::string& a, const std:…
阅读更多...
数据结构与算法—空间复杂度详解与示例（C#，C++）

数据结构与算法—空间复杂度详解与示例（C#，C++）

文章目录 1. 数据结构概述2. 空间复杂度的定义及影响因素3. 空间复杂度的区分常数空间复杂度&#xff08;O(1)&#xff09;线性空间复杂度&#xff08;O(n)&#xff09;其他空间复杂度 4. 几种典型数据结构的优缺点分析数组&#xff08;Array&#xff09;链表&#xff08;Linke…
阅读更多...
墨迹天气与AI数据湖的集成案例（集易连平台）

墨迹天气与AI数据湖的集成案例（集易连平台）

客户介绍 客户方为国内某皮具生产企业&#xff0c;年设计版型数千款&#xff0c;全国销售门店数一千多家&#xff0c;年销售额达20亿。该AI项目目的是将订单数据、用户行为分析、天气数据、门店位置、客流量等等一系列数据作为AI大模型的输入&#xff0c;经过大模型的训练和…
阅读更多...
压力测试

压力测试

1.什么是压力测试 压力测试考察当前软硬件环境下系统所能承受的最大负荷并帮助找出系统瓶颈所在。压测都是为了系统在线上的处理能力和稳定性维持在一个标准范围内&#xff0c;做到心中有数 使用压力测试&#xff0c;我们有希望找到很多种用其他测试方法更难发现的错误&#…
阅读更多...
【浦语开源】深入探索：大模型全链路开源组件 InternLM Lagent，打造灵笔Demo实战指南

【浦语开源】深入探索：大模型全链路开源组件 InternLM Lagent，打造灵笔Demo实战指南

一、准备工作&#xff1a; 1、环境配置&#xff1a; pip、conda换源&#xff1a; pip临时换源&#xff1a; pip install -i https://mirrors.cernet.edu.cn/pypi/web/simple some-package# 这里的“https://mirrors.cernet.edu.cn/pypi/web/simple”是所换的源&#xff0c;…
阅读更多...
Qt实战项目——贪吃蛇

Qt实战项目——贪吃蛇

一、项目介绍 本项目是一个使用Qt框架开发的经典贪吃蛇游戏&#xff0c;旨在通过简单易懂的游戏机制和精美的用户界面&#xff0c;为玩家提供娱乐和编程学习的机会。 二、主要功能 2.1 游戏界面 游戏主要是由三个界面构成&#xff0c;分别是游戏大厅、难度选择和游戏内界面&a…
阅读更多...
Studio One 6 Professional for Mac v6.6.1 音乐创作编辑软件 激活版

Studio One 6 Professional for Mac v6.6.1 音乐创作编辑软件 激活版

PreSonus Studio One 6 Professional 是一款功能强大的音乐制作软件&#xff0c;它为音乐创作者、制作人、录音师以及音乐爱好者提供了一个全面且易于使用的创作环境。从基本的音频录制到复杂的混音和母带处理&#xff0c;这款软件都能轻松应对&#xff0c;让音乐创作过程变得既…
阅读更多...
『亚马逊云科技产品测评』程序员最值得拥有的第一台专属服务器 “亚马逊EC2实例“

『亚马逊云科技产品测评』程序员最值得拥有的第一台专属服务器 “亚马逊EC2实例“

授权声明&#xff1a;本篇文章授权活动官方亚马逊云科技文章转发、改写权&#xff0c;包括不限于在 Developer Centre, 知乎&#xff0c;自媒体平台&#xff0c;第三方开发者媒体等亚马逊云科技官方渠道 引言 自2006年8月9日&#xff0c;在搜索引擎大会&#xff08;SES San Jo…
阅读更多...
最新文章

Copyright @ 2022~2023