动态规划-子序列问题

简介: 前言在上篇文章我们学习了动态规划的公共子序列问题,现在我们来学习下动态规划的单字符串子序列问题。

「这是我参与2022首次更文挑战的第4天,活动详情查看:2022首次更文挑战


前言


在上篇文章我们学习了动态规划的公共子序列问题,现在我们来学习下动态规划的单字符串子序列问题。


子序列问题


我们直接通过leetcode真题来学习这类题型


当然,我们延续之前的动态规划问题的解题步骤


  1. 定义DP数组及下标含义

  2. 推导递推公式

  3. 初始化DP数组

  4. 遍历生成DP数组

最长回文子串

leetcode-559.png



这是道比较经典的子串问题,有一种解法是通过中心扩散的方式,以每个字符串为中心,求得以其为中心时的最大回文子串。


  1. 定义DP数组及下标含义


我们需要求的是字符串的最大子串,子串并非以开始字符为起点或以结尾字符为终点,我们可以定义DP数组为子串区间的左右边界

const dp = [] // dp[i][j]表示s子区间[i,j]的最长回文子串长度
复制代码

  1. 递归公式推导

  • 当左右边界的值相等时s[i]===s[j]且区间[i + 1, j - 1]是回文,那么此区间
  • 对应的回文长度为dp[i + 1][j - 1] + 2

我们在这边可以通过回文子串长度等于区间长度来判断子串是否为回文

if (s[i] === s[j] && dp[i + 1][j - 1] === (j - 1) - (i + 1) + 1) {
  dp[i][j] = dp[i + 1][j - 1] + 2
}
复制代码

  • 当左右边界值不等或者其子串不是回文时,我们此时的dp值为子串的dp值
dp[i][j] = dp[i + 1][j - 1]
复制代码

  1. DP数组初始化


依题意,我们可以知道当i === j时,其回文子串长度为1,当j === j + 1时,其回文子串长度由i是否和j相等决定

if (i === j) {
  dp[i][j] = 1
}
if (j === i + 1) {
  dp[i][j] === (s[i] === s[j]) ? 2 : 1
}
复制代码

为什么我们要初始化两个值?因为我们在动态规划的公式中出现了dp[i + 1][j - 1],说明当前DP值可能由左下角元素转移而来,而dp[i][i + 1]对应的左下角元素是非法的(左边界大于右边界),所以必须也初始化dp[i][i + 1]

在上篇文章中我们都是先初始化边界值,例如dp[i][0]dp[0][j]。为什么这次可以初始化中间值来解答呢?因为在这是单个字符串的子串问题,对于一个子串来说,我们总是从dp[i][j] // i === j开始向后遍历来避免重复,其实此时的dp[i][i]就是边界值。并且dp[i][j] // j > i是没有意义的,因为其子串为空。所以在后文可以看到,我们遍历生成的DP只会有右上那一半的部分。


  1. 遍历生成DP数组


本题有个难点在于dp[i][j]可以由dp[i + 1][j - 1]转移得到。我们发现其横坐标增加,而纵坐标减少。对应到二维表中,其实就是dp[i][j]是由左下角对应的坐标转移而来的。我们可以先遍历纵坐标,再逆序遍历横坐标来保证左下角的元素有值(边界除外)。

for (let j = 0; j < m; j++) {
  for (let i = j; i >= 0; i--) {
  }
}
复制代码

  1. 完整代码
var longestPalindrome = function(s) {
  // 我们使用两个初始变量来存储答案下标
  let left = 0
  let right = 0
  const m = s.length
  const dp = [] // dp[i][j]表示s区间[i,j]的最长回文子串
  // 双层遍历
  // 外层遍历右边界
  for (let j = 0; j < m; j++) {
    // 内层逆序遍历左边界
    // 左边界应小于等于右边界
    for (let i = j; i >= 0; i--) {
      // DP数组初始化
      if (i === j) {
        dp[i] = []
        dp[i][j] = 1
        continue
      }
      // DP数组初始化
      if (i === j - 1) {
        if (s[i] === s[j]) {
          if (right - left < 1) {
            right = j
            left = i
          }
          dp[i][j] = 2
        } else {
          dp[i][j] = 1
        }
        continue
      }
      // 递推公式
      if (s[i] === s[j] && dp[i + 1][j - 1] === (j - 1) - (i + 1) + 1) {
        dp[i][j] = dp[i + 1][j - 1] + 2
        // 回文串长度大于前值时更新标记坐标
        if (dp[i][j] > right - left + 1) {
          right = j
          left = i
        }
      } else {
        dp[i][j] = dp[i + 1][j - 1]
      }
    }
  }
  return s.slice(left, right + 1)
};
复制代码


我们通过个例子来打印DP数组看看


我们的输出值为babadb,我们将DP中为填表的部分设置为0

for (let i = 0; i < m; i++) {
  for (let j = 0; j < m; j++) {
    if (dp[i][j] === undefined) {
      dp[i][j] = 0
    }
  }
}
复制代码

61.png



可以很清楚地看到只有右上方的表格有数值,其它部分为我们后面添加的0

最长递增子序列


我们再来看个比较简单的题


leetcode-300

60.png


  1. 定义DP数组


我们要求的是数组中的最长递增子序列,那我们可以使用DP记录以nums中元素作为递增子序列结尾的序列长度

const dp = [] // dp[i] 表示以nums[i]作为最后元素的递增子序列长度
复制代码

  1. 推导递推公式


依照题意其实可以推出,我们要求以nums[i]为结尾的最大递增子序列长度,那其长度可以由它之前的比其小的元素作为结尾的子序列+1得到。

dp[i] = Math.max(dp[0...j]) + 1 // 其中nums[j] < nums[i]
复制代码

  1. DP数组初始化


我们可以知道,对于第一个元素来说,以其结尾的最长递增子序列为[nums[0]],其长度为1。同时我们可以知道,对于每个元素来说,其最短的递增子序列为nums[i],其长度为1。所以为了方便后面比较,我们将所有值都初始化为1

dp = new Array(nums.length).fill(1)
复制代码
  1. DP数组生成

我们当前dp值可以由其之前的任意元素转化,所以我们需要两重遍历


for (let i = 0; i < m; i++) {
  for (let j = 0; j < i; j++) {
    // ...
  }
}
复制代码



  1. 完整代码
var lengthOfLIS = function(nums) {
  const m = nums.length
  // dp定义及初始化
  const dp = new Array(m).fill(1)
  // max变量用于标记最大长度
  let max = 1
  // 外层遍历数组元素
  for (let i = 0; i < m; i++) {
    // 内层遍历前元素
    for (let j = 0; j < i; j++) {
      // 推导公式
      if (nums[i] > nums[j]) {
        if (dp[i] <= dp[j]) {
          dp[i] = dp[j] + 1
        }
      }
    }
    if (dp[i] > max) {
      max = dp[i]
    }
  }
  return max
};
复制代码


结语


本篇文章学习了动态规划的子序列问题,其中比较经典的就是最长回文串了。下一篇我们将继续学习动态规划的经典题型-打家劫舍。



目录
打赏
0
0
0
0
2
分享
相关文章
从零开始构建:使用Hologres打造个性化推荐系统的完整指南
【10月更文挑战第9天】随着互联网技术的发展,个性化推荐系统已经成为许多在线服务不可或缺的一部分。一个好的推荐系统可以显著提高用户体验,增加用户粘性,并最终提升业务的转化率。本指南将详细介绍如何使用阿里云的Hologres数据库来构建一个高效的个性化推荐系统。我们将涵盖从数据准备、模型训练到实时推荐的整个流程。
417 0
@ExceptionHandler or HandlerExceptionResolver?如何优雅处理全局异常?【享学Spring MVC】(下)
@ExceptionHandler or HandlerExceptionResolver?如何优雅处理全局异常?【享学Spring MVC】(下)
@ExceptionHandler or HandlerExceptionResolver?如何优雅处理全局异常?【享学Spring MVC】(下)
使用Python脚本重命名OSS目录
因为OSS中本质上没有"目录"这一概念,所有对象(Object)都是以键(Key)的形式存储的,目录结构是通过对象键的前缀和分隔符来模拟的。因此,批量重命名目录实际上是批量更改一组对象的键的前缀。具体来说,需要列举特定目录下所有对象以获取它们的键,然后为每个对象生成新的键,这通常包括替换或添加前缀。接下来,通过复制操作将每个对象移到新的键位置,实质上为它们创建了新的键对应的对象。一旦确认所有对象都成功复制,就进行批量删除,移除那些与原始键相对应的对象。本文提供了一个Python脚本用于实现重命名OSS目录。
【操作系统】第三章连续内存分配
【操作系统】第三章连续内存分配
188 0
【操作系统】第三章连续内存分配
shell中date使用总结-基于自动定期备份mysql实践
------------------------时间的格式date [OPTION]... [+FORMAT]echo `date 空格 +'时间格式串'` 调用date必须加符号反引号``,表示执行里面的结果当为: `date +'%Y%m%d-%H:%M:%S'`没有时分秒的情况下,不需要用''将格式包含起来。
865 0
|
9月前
uni-app 181查看好友朋友圈完善(二)
uni-app 181查看好友朋友圈完善(二)
35 1
为Tiny4412设备驱动在proc目录下添加一个可读版本信息的文件
http://blog.csdn.net/morixinguan/article/details/77808088 上节,我们明白了proc文件系统的作用,接下来我们在友善之臂已经写好的led驱动的基础上,在proc目录下创建一个文件夹,然后加入led驱动的版本信息读取。
1397 0
php-fpm进程管理方式(static和dynamic)
目前最新5.3.x的php-fpm,有两种管理进程的方式,分别是static和dynamic。 如果设置成static,进程数自始至终都是pm.max_children指定的数量,pm.start_servers,pm.min_spare_servers,pm.max_spare_servers配置将没有作用。
1065 0
【ASM】多路径(multipath)简介及配置
【ASM】多路径           >>                                   ...
1428 0

热门文章

最新文章