划分型动态规划——分割回文串2

深藏阁楼爱情的钟 2022-10-27 12:06 129阅读 0赞

#  #

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。

返回符合要求的最少分割次数。

示例：

输入: "aab"
    输出: 1
    解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。

### 1、题目分析 ###

从题目提问方式，能够很明显的看出这是个最值类型的和划分类型的动态规划。

### 2、确定状态 ###

最后一步：关注最优策略中最后一段回文串，设为S \[j……N-1\]。需要知道S前j个字符\[0……j-1\]最少可以划分成几个回文串。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]

因此我们可以假设f\[i\]表示S的前i个字符S\[0……i-1\]最少可以划分多少个字符串

### 3、转移方程 ###

假设f\[i\]表示S的前i个字符S\[0……i-1\]最少可以划分多少个字符串

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]

### 4、初始条件和边界情况 ###

初始条件：空串可以被分成0个回文串，f\[0\]=0

### 5、计算顺序 ###

从小到大

### 6、优化 ###

动态规划的转移方程是f\[i\] = minj=0,…,i-1\{f\[j\] + 1| S\[j…i-1\]是回文串\}，每次都判断S\[j……i-1\]是不是回文串会非常的慢，很大程度的加大了时间复杂度。

因此下面采用的优化方式是事先生成回文串，从中间开始，向两边扩招，每次左右两端加上同样的字符。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 2]

从S每一个字符开始向两边扩展，用isPalin\[i\]\[j\]表示S\[i…j\]是否是回文串，最终时间复杂度降为O(N\*N)。

### 7、代码实现 ###

class Solution:
      
        def minCut(self, s: str) -> int:
            if len(s)==0:
                return 0
            dp = [float('inf') for i in range(len(s)+1)]
            dp[0]=0
            #提前把把判断回文字符串的方法写好！
            for i in range(1,len(s)+1):
                for j in range(i):
                    a=s[j:i]
                    b=s[j:i][::-1]#这里的时间复杂度为n,所以导致最后的时间复杂度为n*n*n
                    if a==b:
                        dp[i]= min(dp[j]+1,dp[i])
            return dp[len(s)]-1
    #执行用时：9176 ms, 在所有 Python3 提交中击败了5.15%的用户
    #内存消耗：14.8 MB, 在所有 Python3 提交中击败了78.04%的用户
    
    #优化之后的代码
    def isPath(s:str):
        n = len(s)
        dp = [[0]*n for i in range(n)]
        for i in range(n):
            k=l=i
            while k>=0 and l<n and s[k]==s[l]:
                dp[k][l]=1
                k=k-1
                l=l+1
        for i in range(n):
            k=i
            l=i+1
            while k>=0 and l<n and s[k]==s[l]:
                dp[k][l]=1
                k=k-1
                l=l+1
        return dp
    class Solution:
        def minCut(self, s: str) -> int:
            if len(s)==0:
                return 0
            dp = [float('inf') for i in range(len(s)+1)]
            dp[0]=0
            dp1=isPath(s)
            for i in range(1,len(s)+1):
                for j in range(i):
                    if dp1[j][i-1]==1:
                        dp[i]= min(dp[j]+1,dp[i])
            return dp[len(s)]-1

#  #

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70]: /images/20221024/aaa8ba071ef14a23a5287a642b5237a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 1]: /images/20221024/420a23e47e3542c399f42ddad0c92d82.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQwODc1MDc4_size_16_color_FFFFFF_t_70 2]: /images/20221024/843e974553114bbf968f6cb92dabf2ea.png