wordpress漂亮手机网站模板下载韶关网站推广

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

wordpress漂亮手机网站模板下载,韶关网站推广,深圳中小企业网站制作,开发一个棋牌app需要多少钱文章目录 一、引言二、动态规划方法论深度提炼子序列问题的通用解法模式 三、通用方法论应用示例#xff1a;最长递增子序列#xff08;LeetCode题目300#xff09;Go 语言代码实现 四、最长连续递增序列#xff08;LeetCode题目674#xff09;Go 语言代码实现 五、最长重… 文章目录 一、引言二、动态规划方法论深度提炼子序列问题的通用解法模式 三、通用方法论应用示例最长递增子序列LeetCode题目300Go 语言代码实现 四、最长连续递增序列LeetCode题目674Go 语言代码实现 五、最长重复子数组LeetCode题目718Go 语言代码实现 六、最长公共子序列LeetCode题目1143Go 语言代码实现 七、最大子序和LeetCode题目53Go 语言代码实现 八、判断子序列LeetCode题目392Go 语言代码实现 九、不同的子序列LeetCode题目115Go 语言代码实现 十、两个字符串的删除操作LeetCode题目583Go 语言代码实现 十一、编辑距离LeetCode题目72Go 语言代码实现 十二、回文子串LeetCode题目647Go 语言代码实现 十三、最长回文子序列LeetCode题目516Go 语言代码实现 十四、结论 一、引言 在LeetCode的算法题中子序列相关的问题广泛存在例如“最长递增子序列”、“最长公共子序列”等。这些问题虽然具体题意不同但本质上都可通过动态规划Dynamic Programming, DP来解决。动态规划是一种通过分解子问题并重用子问题解的算法技术非常适用于这类具有“最优子结构”的问题。 本篇文章将以多个典型的LeetCode题目为例逐步提炼出解决子序列问题的通用方法论帮助您系统掌握动态规划解决子序列问题的核心技巧。 力扣LeetCode题目的链接列表

1. 最长递增子序列674. 最长连续递增序列718. 最长重复子数组1143. 最长公共子序列53. 最大子序和392. 判断子序列115. 不同的子序列583. 两个字符串的删除操作72. 编辑距离647. 回文子串516. 最长回文子序列 二、动态规划方法论深度提炼 动态规划解题方法通常包含以下四个核心步骤 确定子问题识别问题的子问题如何划分并使得较小问题的解可复用于较大问题的解。构建最优子结构确保通过每个子问题的最优解组合得到整个问题的最优解。定义状态转移方程状态转移方程是动态规划的核心通过它定义出从一个子问题解递推到另一个子问题解的规则。初始化和递归顺序设置初始值明确递归或迭代顺序。 子序列问题的通用解法模式 在LeetCode的子序列问题中动态规划的具体实现有以下共通模式 dp数组的定义dp数组一般用来表示问题最优解中的特定属性例如“最长子序列长度”、“出现次数”、“和”等。dp数组的定义决定了每个子问题的状态表示。状态转移方程设计 对于“最长递增子序列”类问题通常通过比较当前元素与前面元素的关系递推得到最长子序列的长度。对于“最长公共子序列”类问题通常根据两个字符串的字符是否相等来递归或迭代。对于“编辑距离”类问题通常需要综合增删改三种操作的最小代价。 初始化与递归顺序大部分问题中dp数组会有边界初始值或特定的初始化设定并采用自底向上或自顶向下的递归顺序。 三、通用方法论应用示例最长递增子序列LeetCode题目300 题目描述 题意给定一个整数数组nums找到其中最长的严格递增子序列的长度。 示例 输入: nums [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长递增子序列之一是 [2,3,7,101]因此长度为 4。解题思路 dp数组定义我们定义dp[i]为以nums[i]结尾的最长递增子序列的长度。状态转移方程对于每一个i遍历0到i-1的所有元素j如果nums[j] nums[i]则可以将nums[i]接在以nums[j]结尾的递增子序列后面因此有dp[i] max(dp[i], dp[j] 1)。初始化由于单个元素本身也是一个递增子序列因此dp数组的每个元素初始值都设为1。递归顺序从前往后遍历每个元素依次计算以每个元素结尾的最长子序列长度。 Go 语言代码实现 func lengthOfLIS(nums []int) int {l : len(nums)result : 1 // 最长递增子序列的长度初始化为1dp : make([]int, l) // dp[i]表示以nums[i]结尾的最长递增子序列长度for i : range dp {dp[i] 1 // 每个位置的递增子序列长度至少为1}for i : 1; i l; i {for j : 0; j i; j {if nums[j] nums[i] { // 只有当nums[i]大于nums[j]时才能构成递增子序列dp[i] max(dp[i], dp[j]1) // 更新dp[i]为最大长度}}if dp[i] result {result dp[i] // 更新全局最长子序列长度}}return result }// 工具函数返回两个整数中的最大值 func max(a, b int) int {if a b {return a}return b }关键要点分析 状态转移方程dp[i] max(dp[i], dp[j] 1)的设计体现了子序列问题的核心思想即将子问题的最优解转移到大问题上。由于每个元素的状态仅依赖于之前的元素因此可以通过嵌套循环递推得到最终解。 四、最长连续递增序列LeetCode题目674 题目描述 给定一个未经排序的整数数组nums找到最长的连续递增子序列子序列是由连续的数字组成的子数组的长度。 示例 输入: nums [1,3,5,4,7] 输出: 3 解释: 最长连续递增子序列是 [1,3,5]长度为3。解题思路 在该问题中关键在于找到连续递增的子序列。我们可以使用动态规划DP来实现 dp数组定义定义dp[i]为以nums[i]结尾的最长连续递增子序列的长度。状态转移方程如果nums[i] nums[i-1]说明当前元素可以与前一个元素构成递增子序列因此dp[i] dp[i-1] 1。否则dp[i]重置为1表示以nums[i]结尾的新起始子序列。初始化每个位置的递增序列至少包含自身一个元素因此将所有dp[i]初始化为1。递归顺序从左到右遍历数组每次更新dp[i]的值。 Go 语言代码实现 func findLengthOfLCIS(nums []int) int {l : len(nums)if l 0 {return 0}dp : make([]int, l) // dp[i]表示以nums[i]结尾的最长连续递增子序列长度for i : range dp {dp[i] 1 // 初始化为1}result : 1 // 用于存储最长连续递增子序列的长度for i : 1; i l; i {if nums[i] nums[i-1] { // 如果当前元素大于前一个元素dp[i] dp[i-1] 1 // 累加前一个子序列的长度} else {dp[i] 1 // 否则重置为1重新开始}if dp[i] result {result dp[i] // 更新全局最长长度}}return result }关键要点分析 在该题中连续递增的特点使得状态转移方程更为简单。我们只需判断当前元素和前一元素的关系以确定是否延续或重新开始子序列。result变量用于存储最长的连续递增子序列长度确保在遍历中随时得到最终解。 五、最长重复子数组LeetCode题目718 接下来我们将介绍最长重复子数组问题这一题与前面的最长递增序列问题有所不同因为它涉及两个数组的匹配问题。 题目描述 给定两个整数数组nums1和nums2返回两个数组中公共的、长度最长的重复子数组的长度。 示例 输入: nums1 [1,2,3,2,1], nums2 [3,2,1,4,7] 输出: 3 解释: 长度最长的重复子数组是 [3,2,1]长度为3。解题思路 dp数组定义我们定义dp[i][j]为在nums1中以第i-1位结尾和在nums2中以第j-1位结尾的最长重复子数组的长度。状态转移方程如果nums1[i-1] nums2[j-1]则dp[i][j] dp[i-1][j-1] 1否则dp[i][j] 0。初始化dp[i][0]和dp[0][j]初始化为0因为任一数组为空时没有公共子数组。递归顺序从左到右、从上到下填充二维dp数组并在过程中记录最长的子数组长度。 Go 语言代码实现 func findLength(nums1 []int, nums2 []int) int {l1, l2 : len(nums1), len(nums2)dp : make([][]int, l11) // dp[i][j]表示以nums1[i-1]和nums2[j-1]结尾的最长重复子数组长度for i : range dp {dp[i] make([]int, l21)}result : 0 // 用于记录最长重复子数组的长度for i : 1; i l1; i {for j : 1; j l2; j {if nums1[i-1] nums2[j-1] { // 如果两数组对应位置的元素相等dp[i][j] dp[i-1][j-1] 1 // 延长前一个子数组的长度if dp[i][j] result {result dp[i][j] // 更新全局最长长度}} else {dp[i][j] 0 // 否则没有公共子数组重置为0}}}return result }关键要点分析 该题的dp数组使用二维结构以便对比nums1和nums2的每个位置组合。每次找到一个相同元素时延长重复子数组的长度否则将当前子问题解置零。通过对dp数组的累积更新记录并获取最长的公共子数组长度。 好的接下来是最长公共子序列问题LeetCode题目1143的详细解析。 六、最长公共子序列LeetCode题目1143 题目描述 给定两个字符串text1和text2返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列则返回0。子序列不要求在原字符串中是连续的但顺序必须一致。 示例 输入: text1 abcde, text2 ace 输出: 3
   解释: 最长公共子序列是 ace因此返回3。解题思路 最长公共子序列问题与前面的最长重复子数组不同它关注的是子序列不连续的匹配而不是子数组连续的匹配。该问题可使用动态规划解决步骤如下 dp数组定义定义dp[i][j]为字符串text1前i个字符和字符串text2前j个字符的最长公共子序列的长度。状态转移方程如果text1[i-1] text2[j-1]则dp[i][j] dp[i-1][j-1] 1否则dp[i][j] max(dp[i-1][j], dp[i][j-1])。这个方程表示如果当前字符匹配则可以在前一个状态基础上延长子序列如果不匹配则取两个可能情况的最大值。初始化如果任一字符串为空即dp[i][0]或dp[0][j]则公共子序列长度为0。递归顺序按行或按列填充二维dp数组。 Go 语言代码实现 func longestCommonSubsequence(text1, text2 string) int {l1, l2 : len(text1), len(text2)dp : make([][]int, l11) // dp[i][j]表示text1前i个字符和text2前j个字符的最长公共子序列长度for i : range dp {dp[i] make([]int, l21)}for i : 1; i l1; i {for j : 1; j l2; j {if text1[i-1] text2[j-1] { // 当两个字符相等时dp[i][j] dp[i-1][j-1] 1 // 延长公共子序列长度} else {dp[i][j] max(dp[i-1][j], dp[i][j-1]) // 否则取相邻位置的最大长度}}}return dp[l1][l2] // 返回最长公共子序列的长度 }// 工具函数返回两个整数中的最大值 func max(a, b int) int {if a b {return a}return b }关键要点分析 状态转移方程的设计清晰表达了最长公共子序列的递归关系当两个字符匹配时可通过延长已有公共子序列长度获得新解。dp[i][j]的计算依赖于其左、上和左上方位置的值因此填充顺序需从左到右、从上到下。通过遍历dp数组的终点值即dp[l1][l2]得到最长公共子序列的长度。 七、最大子序和LeetCode题目53 接下来我们介绍最大子序和问题这是一个经典的动态规划问题要求在一个数组中找到连续子数组的最大和。 题目描述 给定一个整数数组nums找到具有最大和的连续子数组并返回其和。 示例 输入: nums [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大为 6。解题思路 该题目要求寻找最大子序和属于“区间最大和”问题。可以通过动态规划来解决 dp数组定义定义dp[i]为以nums[i]结尾的最大子序和。状态转移方程若前一个位置的dp[i-1]值大于0则将其加入当前元素形成新子数组否则当前元素单独作为新子序列的起点。因此dp[i] max(dp[i-1] nums[i], nums[i])。初始化dp[0] nums[0]因为以第一个元素结尾的最大子序和即为nums[0]。递归顺序从左到右遍历数组逐步累积计算最大和。 Go 语言代码实现 func maxSubArray(nums []int) int {l : len(nums)dp : make([]int, l) // dp[i]表示以nums[i]结尾的最大子序和dp[0] nums[0]result : nums[0] // 存储全局最大和for i : 1; i l; i {dp[i] max(dp[i-1]nums[i], nums[i]) // 更新dp[i]为当前最大和if dp[i] result {result dp[i] // 更新全局最大和}}return result }关键要点分析 该题的dp数组设计特别之处在于它在每一步选择是否将前面的子序列结果带入当前状态。状态转移方程中的max(dp[i-1] nums[i], nums[i])确保了我们每一步都可以选择“重开”子序列或“延续”已有的子序列从而实现最优子结构。 八、判断子序列LeetCode题目392 最后我们来看一个简单但巧妙的子序列问题即如何判断一个字符串是否是另一个字符串的子序列。 题目描述 给定字符串s和t判断s是否是t的子序列。可以假设两个字符串均仅包含英文小写字母。 示例 输入: s abc, t ahbgdc 输出: true 解释: s 是 t 的子序列。解题思路 这个问题不需要完整的动态规划来解决因为子序列要求顺序一致但不连续。我们可以通过双指针或DP判断每个字符的匹配情况。 dp数组定义使用双指针分别遍历s和t若s[i] t[j]则移动s的指针否则仅移动t的指针。状态转移方程无经典的DP状态转移方程本题可用指针遍历简化实现。初始化双指针从字符串起始位置开始。递归顺序顺序遍历s和t。 Go 语言代码实现 //动态规划 func isSubsequence1(s, t string) bool {ls, lt : len(s), len(t)dp : make([][]int, ls1)var maxLength intfor i : range dp {dp[i] make([]int, lt1)}for i : 1; i ls; i {for j : 1; j lt; 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]}if maxLength dp[i][j] {maxLength dp[i][j]}}}return maxLength ls } //双指针 func isSubsequence(s, t string) bool {i, j : 0, 0ls, lt : len(s), len(t)for i ls j lt {if s[i] t[j] { // 若字符匹配移动s的指针i}j // 始终移动t的指针}return i ls // 若s的指针移动到末尾则s是t的子序列 }关键要点分析 双指针法在保证正确性的前提下以最优复杂度O(n)解决了子序列判定问题。相较于完整的DP表结构双指针方法简洁且高效非常适合子序列匹配类问题。 好的接下来我们继续介绍 不同的子序列LeetCode题目115的问题及其解法。 九、不同的子序列LeetCode题目115 题目描述 给定一个字符串s和一个字符串t计算在s的子序列中t出现的个数。 示例 输入: s rabbbit, t rabbit 输出: 3 解释: 如下图所示有 3 种可以从 s 中得到 rabbit 的方式。解题思路 在该题中我们需要统计t在s中作为子序列出现的次数。可以使用动态规划通过分析字符是否匹配递推出每个子问题的解。具体步骤如下 dp数组定义定义dp[i][j]为s的前i个字符中t的前j个字符出现的次数。状态转移方程 当s[i-1] t[j-1]时dp[i][j] dp[i-1][j-1] dp[i-1][j]表示当前字符相等时子序列可以选择匹配当前字符或忽略当前字符当s[i-1] ! t[j-1]时dp[i][j] dp[i-1][j]表示字符不匹配的情况下只能通过忽略当前字符来求解。 初始化dp[i][0] 1即t为空时是任何字符串的子序列子序列出现次数为1。递归顺序按行遍历dp表以自顶向下、自左向右的顺序填充。 Go 语言代码实现 func numDistinct(s string, t string) int {ls, lt : len(s), len(t)dp : make([][]int, ls1) // dp[i][j]表示s的前i个字符中包含t的前j个字符的子序列个数for i : range dp {dp[i] make([]int, lt1)dp[i][0] 1 // 当t为空字符串时是s的子序列}for i : 1; i ls; i {for j : 1; j lt; 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] // 不匹配时忽略s的当前字符}}}return dp[ls][lt] }关键要点分析 该题的动态规划表格通过字符匹配与否确保了子序列匹配的所有可能组合都被考虑。通过逐层累积每一子问题的最优解dp[ls][lt]即为s中出现t的所有方式。 十、两个字符串的删除操作LeetCode题目583 接下来我们将探讨两个字符串的删除操作这一问题该题的本质是在两个字符串之间寻找相似部分从而最小化删除次数。 题目描述 给定两个单词word1和word2返回使得两个单词相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。 示例 输入: word1 sea, word2 eat 输出: 2 解释: 将 sea 变为 ea 并删除 t最少需要 2 步。解题思路 该题的核心在于最小化两个字符串的删除操作具体实现可以通过找到最长公共子序列来进行。步骤如下 dp数组定义定义dp[i][j]为将word1的前i个字符与word2的前j个字符变为相同所需的最小步数。状态转移方程 当word1[i-1] word2[j-1]时字符相等不需删除操作故dp[i][j] dp[i-1][j-1]当word1[i-1] ! word2[j-1]时考虑删除一个字符后使得剩余字符匹配的最小代价故dp[i][j] min(dp[i-1][j], dp[i][j-1]) 1。 初始化dp[i][0] i表示word2为空时需要删除word1的所有字符同理dp[0][j] j。递归顺序从左到右逐步构建二维dp表。 Go 语言代码实现 func minDistance(word1 string, word2 string) int {l1, l2 : len(word1), len(word2)dp : make([][]int, l11) // dp[i][j]表示将word1的前i个字符与word2的前j个字符变为相同所需的最小步数for i : range dp {dp[i] make([]int, l21)dp[i][0] i // 初始化第一列}for j : range dp[0] {dp[0][j] j // 初始化第一行}for i : 1; i l1; i {for j : 1; j l2; 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]) 1 // 选择删除的最小代价}}}return dp[l1][l2] }// 工具函数返回两个整数中的较小值 func min(a, b int) int {if a b {return a}return b }关键要点分析 该问题可以看作是“编辑距离”的简化版主要涉及删除操作因此只需考虑删除的最小代价。dp[i][j]记录了当前最小步数并通过累积前面的最小操作实现了从局部最优解推向全局最优解。 十一、编辑距离LeetCode题目72 编辑距离是经典的动态规划问题之一主要关注插入、删除和替换操作的最小代价。 题目描述 给定两个单词word1和word2计算将word1转换成word2所需的最小操作数。可以对一个单词执行插入、删除或替换操作。 示例 输入: word1 horse, word2 ros 输出: 3 解释: horse - rorse (替换 h 为 r) - rose (删除 r) - ros (删除 e)解题思路 该问题可通过动态规划解决逐步最小化每次编辑的代价 dp数组定义dp[i][j]为将word1的前i个字符变为word2的前j个字符所需的最小编辑次数。状态转移方程 如果word1[i-1] word2[j-1]则无需编辑dp[i][j] dp[i-1][j-1]若不相等则取插入、删除、替换操作的最小代价dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1。 初始化当word2为空时dp[i][0] i同理dp[0][j] j。递归顺序逐步填充整个dp表从左到右、从上到下。 Go 语言代码实现 func minDistance(word1, word2 string) int {l1, l2 : len(word1), len(word2)dp : make([][]int, l11) // dp[i][j]表示将word1的前i个字符变为word2的前j个字符的最小编辑次数for i : range dp {dp[i] make([]int, l21)dp[i][0] i // 初始化第一列}for j : range dp[0] {dp[0][j] j // 初始化第一行}for i : 1; i l1; i {for j : 1; j l2; 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[l1][l2] }// 工具函数返回三个整数中的最小值 func min(a, b, c int) int {if a b {if a c {return a}return c}if b c {return b}return c }关键要点分析 本题动态规划的核心在于清晰的状态转移方程将字符是否匹配的三种编辑操作的最小代价逐步递推。dp[i][j]通过三种操作的最小代价累积得出将word1转换成word2所需的最小编辑距离。 好的接下来我们继续介绍 回文子串LeetCode题目647的问题及其解法。 十二、回文子串LeetCode题目647 题目描述 给定一个字符串s计算并返回s中的回文子串数量。具有相同顺序且相同字符的子串称为回文。 示例 输入: s abc 输出: 3 解释: 回文子串为 [a,b,c]。输入: s aaa 输出: 6 解释: 回文子串为 [a,a,a,aa,aa,aaa]。解题思路 这道题要求我们统计字符串中的回文子串数量可以利用动态规划来判断每个子串是否为回文并记录回文的数量。 dp数组定义定义dp[i][j]表示从字符s[i]到s[j]的子串是否是回文子串。若为回文子串则dp[i][j] true否则为false。状态转移方程 当s[i] s[j]且j - i 1时dp[i][j] true否则当s[i] s[j]且dp[i1][j-1] true时dp[i][j] true。 初始化长度为1的子串均为回文因此对每个位置idp[i][i] true。递归顺序从右下角向左上角遍历dp数组逐步填充。 Go 语言代码实现 func countSubstrings(s string) int {l : len(s)dp : make([][]bool, l) // dp[i][j]表示s从i到j的子串是否为回文for i : range dp {dp[i] make([]bool, l)}result : 0 // 用于记录回文子串的数量for i : l - 1; i 0; i– { // 从右下角到左上角填充dp数组for j : i; j l; j {if s[i] sj {dp[i][j] true // s[i:j1]为回文result // 每找到一个回文子串就计数加一}}}return result }关键要点分析 状态转移方程dp[i][j]结合字符相等性和内部子串的回文性有效判断了每个子串的回文性质。遍历顺序为从右下角到左上角保证每个较短子串的状态在较长子串状态确定前已完成更新。 十三、最长回文子序列LeetCode题目516 最后我们来看一道回文序列问题要求在一个字符串中找到最长的回文子序列长度。 题目描述 给定一个字符串s找到其中最长的回文子序列的长度。子序列不要求是连续的但顺序必须保持一致。 示例 输入: s bbbab 输出: 4 解释: bbbb 是最长的回文子序列。解题思路 该问题可以使用动态规划通过递归判断字符的对称性来解决。 dp数组定义定义dp[i][j]为字符串s从位置i到j的子串的最长回文子序列长度。状态转移方程 若s[i] s[j]则dp[i][j] dp[i1][j-1] 2若s[i] ! s[j]则dp[i][j] max(dp[i1][j], dp[i][j-1])。 初始化对于每个位置idp[i][i] 1即单个字符的回文长度为1。递归顺序从下到上、从左到右填充dp数组保证子问题优先求解。 Go 语言代码实现 func longestPalindromeSubseq(s string) int {l : len(s)dp : make([][]int, l) // dp[i][j]表示s从i到j的最长回文子序列长度for i : range dp {dp[i] make([]int, l)dp[i][i] 1 // 初始化单个字符的回文长度为1}for i : l - 1; i 0; i– { // 从下到上遍历for j : i 1; j l; j { // 从左到右填充if s[i] s[j] {dp[i][j] dp[i1][j-1] 2 // 若字符相等则递推最长回文长度} else {dp[i][j] max(dp[i1][j], dp[i][j-1]) // 否则取左右子问题的最大值}}}return dp[0][l-1] // 返回整个字符串的最长回文子序列长度 }// 工具函数返回两个整数中的最大值 func max(a, b int) int {if a b {return a}return b }关键要点分析 本题通过递归状态方程有效地判断了字符对称性dp[i][j]记录每个子问题的最优解保证子问题递推到全局。本题与最长回文子串问题不同最长回文子序列并不要求子序列连续状态转移时依赖左、下和左下角元素。 十四、结论 在本篇文章中我们系统地梳理了LeetCode中一系列子序列类问题的动态规划解法。通过dp数组定义、状态转移方程设计、初始化、递归顺序等方面我们展示了如何构建并解决常见的子序列问题。动态规划不仅要求细致的代码实现更强调对问题的整体分解与子问题的递推组合这些方法论将有助于提升算法的解决能力。希望本文对您深入理解和掌握动态规划有所帮助