当前位置:   article > 正文

算法|LeetCode(力扣)经典题:动态规划_力扣343题 java 动态规划

力扣343题 java 动态规划

动态规划

更多请查看我的专栏:LeetCode(力扣)刷题指南

可直接在LeetCode中搜索题目名称

img

1.思考状态

​ 先尝试“题目问什么,就把什么设置为状态”。然后考虑“状态如何转移”,如果“状态转移方程”不容易得到,尝试修改定义,目的仍然是为了方便得到“状态转移方程”。

2.思考状态转移方程(核心、难点)

状态转移方程是非常重要的,是动态规划的核心,也是难点,起到承上启下的作用。

技巧是分类讨论。对状态空间进行分类,思考最优子结构到底是什么。即大问题的最优解如何由小问题的最优解得到。

​ 归纳“状态转移方程”是一个很灵活的事情,得具体问题具体分析,除了掌握经典的动态规划问题以外,还需要多做题。

​ 如果是针对面试,请自行把握难度,我个人觉得掌握常见问题的动态规划解法,明白动态规划的本质就是打表格,从一个小规模问题出发,逐步得到大问题的解,并记录过程。动态规划依然是“空间换时间”思想的体现。

3.思考初始化

初始化是非常重要的,一步错,步步错,初始化状态一定要设置对,才可能得到正确的结果。

角度 1:直接从状态的语义出发;

角度 2:如果状态的语义不好思考,就考虑“状态转移方程”的边界需要什么样初始化的条件;

角度 3:从“状态转移方程”方程的下标看是否需要多设置一行、一列表示“哨兵”,这样可以避免一些边界的讨论,使得代码变得比较短。

4.思考输出

有些时候是最后一个状态,有些时候可能会综合所有计算过的状态。

5.思考状态压缩

“状态压缩”会使得代码难于理解,初学的时候可以不一步到位。先把代码写正确,然后再思考状态压缩。

状态压缩在有一种情况下是很有必要的,那就是状态空间非常庞大的时候(处理海量数据),此时空间不够用,就必须状态压缩。

1. 最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。


示例 2:

输入: “cbbd”
输出: "bb”

回文是一个正读和反读都相同的字符串,例如,“aba” 是回文,而“abc” 不是。

1.1 解决方案

方法一:最长公共子串

方法:反转S,使之成为S’,找到S和S’之间最长的公共子串。这也必然是最长的回文子串。

例如:

S=“caba”,S’=“abac”

S和S’之间的最长公共子串为“aba”,恰好是答案

让我们尝试一下这个例子:S =“abacdfgdcaba”,S =“abacdgfdcaba”:

S 以及 S’之间的最长公共子串为“abacd”。显然,这不是回文。

错误:我们可以看到,当S的其他部分中存在非回文子串的反向副本时,最长公共子串法就会失败。

​ 为了纠正这一点,每当我们找到最长的公共子串的候选项时,都需要检查子串的索引是否与反向子串的原始索引相同。如果相同,那么我们尝试更新目前为止找到的最长回文子串;如果不是,我们就跳过这个候选项并继续寻找下一个候选。

复杂度分析

​ 这给我们提供了一个复杂度为 O(n^2)动态规划解法,它将占用 O(n^2)的空间(可以改进为使用 O(n)的空间)。

方法二:暴力法

​ 很明显,暴力法将选出所有子字符串可能的开始和结束位置,并检验它是不是回文。

class Solution:
    # 暴力匹配(超时)
    def longestPalindrome(self, s: str) -> str:
        # 特判
        size = len(s)
        if size < 2:
            return s

        max_len = 1
        res = s[0]

        # 枚举所有长度大于等于 2 的子串
        for i in range(size - 1):
            for j in range(i + 1, size):
                if j - i + 1 > max_len and self.__valid(s, i, j):
                    max_len = j - i + 1
                    res = s[i:j + 1]
        return res

    def __valid(self, s, left, right):
        # 验证子串 s[left, right] 是否为回文串
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

# 超时测试用例
# "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabcaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30

复杂度分析

  • 时间复杂度:O(n^3),假设n是输入字符串的长度,则n(n-1)/2的为此类子字符串(不包括字符本身是回文的一般解法)的总数。因为验证每个子字符串需要O(n) 的时间,所以运行时间复杂度是 O(n^3)。

  • 空间复杂度:O(1)。

方法三:动态规范

​ 为了改进暴力法,我们首先观察如何避免在验证回文时进行不必要的重复计算。考虑 “ababa” 这个示例。如果我们已经知道“bab” 是回文,那么很明显,“ababa” 一定是回文,因为它的左首字母和右尾字母是相同的。

​ 我们给出P(i,j)的定义如下:
P ( i , j ) = { t r u e , 如 果 S i ⋯ S j 是 回 文 子 串 f a l s e , 其 他 情 况 P(i,j)=

{true,SiSjfalse
P(i,j)={ true,SiSjfalse
因此,
P ( i , j ) = ( P ( i + 1 , j − 1 )   

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/709826
推荐阅读
相关标签
  

闽ICP备14008679号