复习回溯算法，深刻体会动态规划

约定不等于承诺〃 2022-10-23 08:29 126阅读 0赞

## 什么是动态规划？ ##

[了解一下再做题][Link 1]  
通过判断每一个字串是否是回文的基础上来判断父串是否是回文，这也就是动态规划的思想——  
**将一个问题拆成几个子问题，分别求解这些子问题，即可推断出大问题的解。**  
[131分割回文][131]  
这道题主要通过先进行判断是否是回文，记录其状态，实现记忆化，本身和回文中间只有一位字符串(比如‘aba’)即是回文，还有一种情况就是在里面是回文的情况下外面也是回文(’aaabaaa‘)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70_pic_center]

## 为什么要动态规划实现记忆法 ##

通过记录字符串的状态，然后下面回溯在进行剪枝的时候可以减少不必要的剪枝

if dp[i][j]:
                        temp.append(s[i:j+1])
                        dfs(j+1)
                        temp.pop(-1)

## Python切片复习一下 ##

【参数1：参数2：参数3】  
参数1是从哪里开始切包括本身，默认从0开始  
参数2是切到哪里，不包括本身，默认从最后一位也就是-1结束  
参数3是步长，整数表示从左往右走，负数表示从右往左走，默认左往右，步长为1

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

# 回溯模板 #

res = []
    path = []
    
    def backtrack(未探索区域, res, path):
        if 未探索区域满足结束条件:
            res.add(path) # 深度拷贝
            return
        for 选择 in 未探索区域当前可能的选择:
            if 当前选择符合要求:
                path.add(当前选择)
                backtrack(新的未探索区域, res, path)
                path.pop()

# 套模板解法 #

class Solution:
        def partition(self, s: str) -> List[List[str]]:
            n = len(s)
            dp = [[False]  *n for _ in range(n)]
    
            for i in range(n):
                for j in range(i+1):
                    if s[i] == s[j] and (j-i<=2 or dp[i+1][j-1]):
                        dp[j][i] = True
            res = []
            temp = []
            def dfs(i):
                if i == n:
                    res.append(temp[:])
                for j in range(i,n):
                    if dp[i][j]:
                        temp.append(s[i:j+1])
                        dfs(j+1)
                        temp.pop(-1)
    
            dfs(0)
            print(res)
            return res

# 巧妙避免深拷贝 #

使用的是产生一个新数组 path + \[s\[:i\]\] ，这样好处是方便：不同的路径使用的是不同的 path，因此不需要 path.pop() 操作；而且 res.append(path) 的时候不用深度拷贝一遍 path。

class Solution:
        def partition(self, s: str) -> List[List[str]]:
            n = len(s)
            dp = [[False] * n for _ in range(n)]
    
            for i in range(n):
                for j in range(i + 1):
                    if (s[i] == s[j]) and (i - j <= 2 or dp[j + 1][i - 1]):
                        dp[j][i] = True
            #print(dp)
            res = []
    
            def helper(i, tmp):
                if i == n:
                    res.append(tmp)
                for j in range(i, n):
                    if dp[i][j]:
                        helper(j + 1, tmp + [s[i: j + 1]])
    
            helper(0, [])
            return res

如果你觉得可以，进阶[132分割][132]

[Link 1]: https://www.zhihu.com/question/23995189
[131]: https://leetcode-cn.com/problems/palindrome-partitioning/solution/fen-ge-hui-wen-chuan-by-leetcode-solutio-6jkv/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221023/9dee74bdf3f24e158304e1258d91507b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]: /images/20221023/3822b8a7df34447e9ffb1dbd694b6b04.png
[132]: https://leetcode-cn.com/problems/palindrome-partitioning-ii/