动态规划经典问题整理

史上最全最丰富的“最长公共子序列”、“最长公共子串”问题的解法与思路https://blog.csdn.net/wangdd_199326/article/details/76464333动态规划-----两个字符串交叉组成第三个字符https://blog.csdn.net/smallfish_love/article/details/52277838动态规划解决01背包问题..........

alim2012

4679人浏览 · 2018-09-15 17:56:28

alim2012 · 2018-09-15 17:56:28 发布

单序列：

最长连续递增序列最长递增子序列最长递增子序列的个数最大子序和
 最大整除子集

爬楼梯最长定差子序列爬楼梯使用最小花费爬楼梯比特位计数旋转数字

把数字翻译成字符串青蛙过河最低加油次数栅栏涂色寻找数组的错位排列

所有子字符串中的元音打家劫舍打家劫舍 II 解决智力问题带因子的二叉树解决智力问题

分隔数组以得到最大和可被三整除的最大和检查数组是否存在有效划分活字印刷填充书架

统计特殊子序列的数目

双序列：

正则表达式匹配最长公共子序列不相交的线最长重复子数组通配符匹配

编辑距离交错字符串同源字符串检测最长等差数列最长的斐波那契子序列的长度判断子序列子序列的数目卖木头块填充书架

区间动态规划：

最少回文分割猜数字大小 II 戳气球为运算表达式设计优先级预测赢家最大平均值和的分组多边形三角剖分的最低得分

状态转移动态规划：

删除一次得到子数组最大和经过一次操作后的最大子数组和最大交替子数组和多米诺和托米诺平铺统计只差一个字符的子串数目学生出勤记录 II

背包问题：

零钱兑换组合总和 Ⅳ 零钱兑换 II 分割等和子集划分为k个相等的子集

. 一和零（双序列背包）目标和单词拆分分汤买钢笔和铅笔的方案数

路径动态规划：

统计全为 1 的正方形子矩阵最大正方形三角形中最小路径之和最大加号标志

最小路径和不同路径 II 地下城游戏 01 矩阵统计农场中肥沃金字塔的数目出界的路径数矩阵中最长的连续1线段出界的路径数 K 站中转内最便宜的航班网格图中递增路径的数目

决策动态规划：

188. 买卖股票的最佳时机 IV
新 21 点 926. 将字符串翻转到单调递增

乘积最大子数组乘积为正数的最长子数组长度丑数 II 优美的排列只有两个键的键盘翻转游戏 II 计算分配糖果的不同方式石子游戏 II

动态规划与树结合：

打家劫舍 III 二叉树中的最长交错路径二叉搜索子树的最大键值和统计可能的树根数目树中距离之和

数位动态规划

至少有 1 位重复的数字不含连续1的非负整数

倍增

Pow(x, n) 在传球游戏中最大化函数值

单序列

1、最长递增子序列

for i in range(1, n):
    for j in range(0, i):
        if nums[j] < nums[i]:
            dp[i] = max(dp[i], dp[j] + 1)
        if dp[i] > maxl:
            maxl = dp[i]

注：采用动态规划的方法的时间复杂度为O(n^2), 最优的方法是采用二分插入的方法如下所示：

LIS = [nums[0]]
for num in nums[1:]:
    if num > LIS[-1]:
        LIS.append(num)
    else:
        index = bisect_left(LIS, num)
        LIS[index] = num
return len(LIS)

如果求单调不递增的子序列还需要num >= LIS[-1] 并且使用bisect_right，见使数组 K 递增的最少操作次数

2、最长递增子序列的个数

nums = [-float('inf')] + nums + [float('inf')]
n = len(nums)
dp = [0] * n
for i in range(0, n - 1):
    for j in range(i + 1, n):
        if nums[j] > nums[i]:
            dp[j] = max(dp[i] + 1, dp[j])

path = [1] + [0] * (n - 1)
for i in range(1, n):
    for j in range(0, i):
        if dp[i] == dp[j] + 1 and nums[i] > nums[j]:
            path[i] += path[j]

return path[-1]

同理，根据1的最优方法，我们可以对2的方法进行优化

3、最长连续递增序列

for i in range(1, n):
    if nums[i - 1] < nums[i]:
        dp[i] = max(dp[i], dp[i - 1] + 1)
    if dp[i] > maxl:
        maxl = dp[i]

4、最大子序和

for i in range(1, n):
    dp[i] = max(dp[i], dp[i - 1] + nums[i])
    if dp[i] > maxl:
        maxl = dp[i]

5、最大整除子集：

for i in range(n):
    for j in range(i + 1, n):
        if nums[j] % nums[i] == 0:
            dp[j] = max(dp[j], dp[i] + 1)

6、最长定差子序列

d = {}
for a in arr:
    d[a] = d.get(a - difference, 0) + 1
return max(d.values())

7、爬楼梯

for i in range(2, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

8、寻找数组的错位排列

for i in range(2, n):
    dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])

9、使用最小花费爬楼梯

for i in range(2, len(cost) + 1):
    dp[i] = min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1])

10、比特位计数

for i in range(1, n + 1):
    if i & 1 == 0:
        dp[i] = dp[i >> 1]
    else:
        dp[i] = dp[i - 1] + 1

11、旋转数字

class Solution:
    def rotatedDigits(self, N: int) -> int:
        ans, dp = 0, [0, 0, 1, -1, -1, 1, 1, -1, 0, 1] + [0] * (N - 9)
        for i in range(N + 1):
            dp[i] = -1 in (dp[i // 10], dp[i % 10]) and -1 or dp[i // 10] | dp[i % 10]
            ans += dp[i] == 1
        return ans

12、打家劫舍 II

a, b = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums) - 1):
    a = max(a + nums[i], b)
    b, a = a, b
res1 = b
a, b = nums[1], max(nums[1], nums[2])
for i in range(3, len(nums)):
    a = max(a + nums[i], b)
    b, a = a, b 
return max(b, res1)

13、解决智力问题

n = len(questions)
dp = [0] * (n + 1)
for i, q in enumerate(questions):
    dp[i + 1] = max(dp[i + 1], dp[i])
    j = min(i + q[1] + 1, n)
    dp[j] = max(dp[j], dp[i] + q[0])
return dp[n]

14、栅栏涂色

if n == 1: return k
dp = [0] * (n + 1)
dp[1], dp[2] = k, k * k
for i in range(3, n + 1):
    dp[i] = dp[i - 1] * (k - 1) + dp[i - 2] * (k - 1)
return dp[-1]

15、带因子的二叉树

arr.sort()
for i, a in enumerate(arr):
    dp[a] = 1
    for j in range(i):
        if a % arr[j] == 0 and a // arr[j] in set(arr):
            dp[a] += dp[arr[j]] * dp[a // arr[j]]

return sum(count for num, count in dp.items())

16、分隔数组以得到最大和

n = len(arr)
dp = [0] * (n + 1)
for i in range(1, n + 1):
    maxl = 0
    for j in range(i - 1, max(i - k, 0) - 1, - 1):
        maxl = max(maxl, arr[j])
        dp[i] = max(dp[i], dp[j] + maxl * (i - j))
return dp[-1]

17、可被三整除的最大和

dp = [0] * div
for n in nums:
    nw = [0] * div
    for d in range(div):
        nw[d] = dp[d] + n
    for t in nw:
        dp[t % div] = max(dp[t % div], t)    
return dp[0]

18、检查数组是否存在有效划分

dp = [True] + [False] * len(nums)
for i in range(1, len(nums)):
    dp[i + 1] |= dp[i - 1] and nums[i] == nums[i - 1]
    dp[i + 1] |= dp[i - 2] and nums[i] == nums[i - 1] and nums[i] == nums[i - 2]
    dp[i + 1] |= dp[i - 2] and nums[i] - nums[i - 1] == 1 and nums[i - 1] - nums[i - 2] == 1
return dp[-1]

该题也可以用贪心去做，但是贪心的过程较为繁琐，而且时间复杂度也为O(n)

19、活字印刷（动态规划 + 组合数学）

dp, cv, alllen = [1] + [0] * len(tiles), Counter(tiles).values(), 0
for v in cv:
    alllen += v
    for i in range(alllen, 0, -1): 
        dp[i] += sum(dp[i - j] * math.comb(i, j) for j in range(1, min(i,v) + 1))
return sum(dp) - 1

20、填充书架

for i in range(1, len(books) + 1):
    tmp_width, j, h = 0, i, 0
    while j > 0:
        tmp_width += books[j - 1][0]
        if tmp_width > shelf_width:
            break
        h = max(h, books[j - 1][1])
        dp[i] = min(dp[i], dp[j - 1] + h)
        j -= 1
return dp[-1]

21、统计特殊子序列的数目

class Solution:
    def countSpecialSubsequences(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        f0 = f1 = f2 = 0
        for num in nums:
            if num == 0:
                f0 = (f0 * 2 + 1) % mod
            elif num == 1:
                f1 = (f1 * 2 + f0) % mod
            else:
                f2 = (f2 * 2 + f1) % mod
        return f2

双序列

1、最长公共子序列

for i in range(1, len(text1) + 1):
    for j in range(1, len(text2) + 1):
        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])

2、不相交的线

for i in range(1, len(nums1) + 1):
    for j in range(1, len(nums2) + 1):
        if nums1[i - 1] == nums2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

3、最长重复子数组

m, n = len(nums1), len(nums2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
maxl = 0
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if nums1[i - 1] == nums2[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        if dp[i][j] > maxl:
            maxl = dp[i][j]
return maxl

注：使用滑动窗口的方法可以使时间复杂度降到O((m + n) *min(m, n)), 空间复杂度降为O(1)

m, n = len(nums1), len(nums2)
maxl = 0
for d in range(1 - m, n):
    l = 0
    for i in range(max(0, -d), min(m, n - d)):
        if nums1[i] == nums2[i + d]:
            l += 1
            maxl = max(maxl, l)
        else: l = 0
return maxl

还可以使用二分查找+哈希的方法使得时间复杂度降为O((m + n) *log(min(m, n)))

4、通配符匹配

for i in range(1, len(p) + 1):
    for j in range(1, len(s) + 1):
        if p[i - 1] == '?':
            dp[i][j] = dp[i - 1][j - 1]
        elif p[i - 1] == '*':
            dp[i][j] = dp[i - 1][j] or dp[i - 1][j - 1] or dp[i][j - 1]
        elif p[i - 1] == s[j - 1]:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][j] = False

5、正则表达式匹配

for i in range(1, len(p) + 1):
    for j in range(1, len(s) + 1):
        if p[i - 1] == s[j - 1] or p[i - 1] == '.':
            dp[i][j] = dp[i - 1][j - 1]
        elif p[i - 1] == '*':
            if p[i - 2] == s[j - 1] or p[i - 2] == '.':
                dp[i][j] = dp[i - 2][j] or dp[i][j - 1]
            else:
                dp[i][j] = dp[i - 2][j]
        else:
            dp[i][j] = False

6、最长等差数列

dp = dict()
for cur in range(1, len(nums)):
    for prev in range(cur):
        diff = nums[cur] - nums[prev]
        dp[(cur, diff)] = dp.get((prev, diff), 1) + 1
return max(dp.values())

7、最长的斐波那契子序列的长度

index = {x: i for i, x in enumerate(A)}
longest = collections.defaultdict(lambda: 2)

ans = 0
for k, z in enumerate(A):
    for j in range(k):
        i = index.get(z - A[j], None)
        if i is not None and i < j:
            cand = longest[j, k] = longest[i, j] + 1
            ans = max(ans, cand)

return ans if ans >= 3 else 0

8、判断子序列

for i in range(1, len(s) + 1):
    for j in range(1, len(t) + 1):
        if s[i - 1] == t[j - 1]:
            dp[i][j] = dp[i - 1][j - 1]
        else:
            dp[i][j] = dp[i][j - 1]

该方法可以使用双指针进行求解

9、子序列的数目

for i in range(1, len(t) + 1):
    for j in range(i, len(s) + 1):
        if t[i - 1] == s[j - 1]:
            dp[j] = dp[i - 1][j - 1] + dp[i][j - 1]
        else:
            dp[j] = dp[i][j - 1]

10、通过删除字母匹配到字典里最长单词

类似于判断子序列，可以采用双指针进行求解，本题是一个长串匹配多个短串，可以采用动态的方法构造状态转移矩阵，减少长串指针的空跳

构造过程：

m, set_s = len(s), set(s)
f = [defaultdict(lambda: m) for _ in range(m + 1)]

for i in reversed(range(m)):
    for c in set_s:
        if s[i] == c:
            f[i][ord(c) - ord('a')] = i
        else:
            f[i][ord(c) - ord('a')] = f[i + 1][ord(c) - ord('a')]

匹配过程：

res = ""
for t in dictionary:
    match = True
    j = 0
    for i in range(len(t)):
        if f[j][ord(t[i]) - ord('a')] == m:
            match = False
            break
        j = f[j][ord(t[i]) - ord('a')] + 1
    if match:
        if len(t) > len(res) or (len(t) == len(res) and t < res):
            res = t
return res

11、交错字符串

for i in range(len(s1) + 1):
    for j in range(len(s2) + 1):
        if i > 0 and s1[i - 1] == s3[i + j - 1]:
            dp[i][j] = dp[i][j] or dp[i - 1][j]
        if j > 0 and s2[j - 1] == s3[i + j - 1]:
            dp[i][j] = dp[i][j] or dp[i][j - 1]

12、编辑距离

for i in range(1, len(word1)+1):
    for j in range(1, len(word2)+1):
        if word1[i - 1] == word2[j - 1]:
            dp[i][j] = dp[i - 1][j -1]
        else:
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + 1)

13、卖木头块

for i in range(1, m + 1):
    for j in range(1, n + 1):
        dp[i][j] = mp[i, j]
        for k in range(1, j + 1):
            dp[i][j] = max(dp[i][j], dp[i][j - k] + dp[i][k])
        for l in range(1, i + 1):                      
            dp[i][j] = max(dp[i][j], dp[i - l][j] + dp[l][j])

区间动态规划

1、猜数字大小 II

for j in range(2, n + 1):
    for i in reversed(range(1, j)):             
        f[i][j] = min(max(f[i][x - 1], f[x + 1][j]) + x for x in range(i, j))
return f[1][n]

2、最少回文分割

#求取区间是否是回文串
for l in range(n-1, -1, -1):
    for r in range(l + 1, n):
        if s[l] == s[r]:
            if l + 1 == r:
                f[l][r] = True
            else:
                f[l][r] = f[l + 1][r - 1]

#求取最小分割
for i in range(1, len(s)):
    dp[i] = 0 if f[0][i] else i
    for j in range(1, i + 1):
        if f[j][i]:
            dp[i] = min(dp[i], dp[j - 1] + 1)

3、戳气球

for i in reversed(range(n)):
    for j in range(i + 2, n + 2):
        for k in range(i + 1, j):
            val = nums[i] * nums[k] * nums[j]
            dp[i][j] = max(dp[i][j], dp[i][k] + dp[k][j] + val)

4、为运算表达式设计优先级

nums = [int(num) for num in re.split("[+\-*]", input)]
opts = re.sub('[0-9]', "", input)
opt_m = {'+':(lambda x, y:x+ y), '-':(lambda x, y:x - y), '*':(lambda x, y:x * y)}
dp = [[[] for _ in range(len(nums))] for _ in range(len(nums))]


for j in range(len(nums)):
    for i in reversed(range(j + 1)):
        if i == j:
            dp[i][j].append(nums[i])
        else:
            for k in range(i, j):                   
                dp[i][j].extend([opt_m[opts[k]](x,y) for x, y in product(dp[i][k], dp[k + 1][j])])

5、预测赢家

length = len(nums)
dp = [[0] * length for _ in range(length)]
for i, num in enumerate(nums):
    dp[i][i] = num
for i in range(length - 2, -1, -1):
    for j in range(i + 1, length):
        dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1])
return dp[0][length - 1] >= 0

6、最大平均值和的分组

P, N = [0], len(nums)
for x in nums: P.append(P[-1] + x)
def average(i, j):
    return (P[j] - P[i]) / float(j - i)

dp = [average(i, N) for i in range(N)]
for k in range(K-1):
    for i in range(N):
        for j in range(i+1, N):
            dp[i] = max(dp[i], average(i, j) + dp[j])

return dp[0]

7、多边形三角剖分的最低得分

n = len(A)
dp = [[inf] * n for _ in range(n)]
for i in range(n - 1):
    dp[i][i + 1] = 0
for i in reversed(range(n)):
    for j in range(i + 2, n):
        for k in range(i + 1, j):
            dp[i][j] = min(dp[i][j], dp[i][k] + A[i] * A[k] * A[j] + dp[k][j])
return dp[0][-1]

状态转移动态规划

1、删除一次得到子数组最大和

dp0, dp1, ans = arr[0], 0, arr[0]
for i in arr[1:]:
    dp1 = max(dp1 + i, dp0)
    dp0 = max(dp0 + i, i)
    ans = max(ans, dp0, dp1)
return ans

2、删除一次得到子数组最大和

dp0, dp1 = nums[0], max(nums[0], nums[0] ** 2)
maxl = max(dp0, dp1)
for i in range(1, len(nums)):
    dp1 = max(dp1 + nums[i], max(dp0, 0) + nums[i] ** 2)
    dp0 = max(dp0 + nums[i], nums[i])
    maxl = max(maxl, dp0, dp1)
return maxl

3、最大交替子数组和

ans, dp0, dp1 = nums[0], nums[0], -inf
for num in nums[1:]:
    dp0, dp1 = max(num, dp1 + num), dp0 - num
    ans = max(ans, dp0, dp1)
return ans

4、多米诺和托米诺平铺

#dp1[k] 总计k列，最后一列满的种数
#dp2[k] 总计k列，最后一列差一个满
dp1, dp2 = [0] * (max(3, n + 1)), [0] * (max(3, n + 1))
dp2[1], dp2[2] = 0, 2
dp1[1], dp1[2] = 1, 2
for i in range(3, n + 1):
    dp2[i] = dp2[i - 1] + 2 *dp1[i - 2]
    dp1[i] = dp1[i - 1] + dp1[i - 2] + dp2[i - 1]
return dp1[n] % (10 ** 9 + 7)

5、统计只差一个字符的子串数目

cnt[i-1][j-1]为以s[i-1]和t[j-1]结尾的恰好只有一个字符不同的子串对数目，same[i][j]记录以s[i]和t[j]结尾的连续相同的字符数量。

class Solution:
    def countSubstrings(self, s: str, t: str) -> int:
        m, n = len(s), len(t)
        dp = [(0, 0)]*(n+1) # 记录 (以s[i]和t[j]结尾的 满足条件的子字符串对数目, 连续相同的位数)
        tot = 0   # 总的满足条件的子字符串对数目
        for i in range(m):
            last = dp[0]
            for j in range(n):
                if s[i] == t[j]:
                    cur = (dp[j][0], dp[j][1] + 1)
                    tot += dp[j][0]
                else:
                    cur = (dp[j][1] + 1, 0)
                    tot += dp[j][1] + 1
                dp[j], last = last, cur
            dp[n] = last
        return tot

6、学生出勤记录 II

class Solution:
    def checkRecord(self, n: int) -> int:
        mod = 10 ** 9 + 7
        dp = [[0] * 2  for _ in range(3)]
        dp[0][0] = 1
        for i in range(n):
            tp = [[0] * 2  for _ in range(3)]
            #以A为结尾
            for j in range(3):
                tp[0][1] = (tp[0][1] + dp[j][0]) % mod
            
            #以P为结尾
            for j in range(3):
                for k in range(2):
                    tp[0][k] = (tp[0][k] + dp[j][k]) % mod

            #以L为结尾
            for j in range(1, 3):
                for k in range(2):
                    tp[j][k] = (tp[j][k] + dp[j - 1][k]) % mod
                  
            dp = tp
        return sum([sum(p) for p in dp]) % mod

本题还可以使用快速幂的方法将时间复杂度降为O(logn)

代码如下：

class Solution:
    def checkRecord(self, n: int) -> int:
        MOD = 10**9 + 7
        mat = [
            [1, 1, 0, 1, 0, 0],
            [1, 0, 1, 1, 0, 0],
            [1, 0, 0, 1, 0, 0],
            [0, 0, 0, 1, 1, 0],
            [0, 0, 0, 1, 0, 1],
            [0, 0, 0, 1, 0, 0],
        ]
        
        def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
            rows, columns, temp = len(a), len(b[0]), len(b)
            c = [[0] * columns for _ in range(rows)]
            for i in range(rows):
                for j in range(columns):
                    for k in range(temp):
                        c[i][j] += a[i][k] * b[k][j]
                        c[i][j] %= MOD
            return c
        
        def matrixPow(mat: List[List[int]], n: int) -> List[List[int]]:
            ret = [[1, 0, 0, 0, 0, 0]]
            while n > 0:
                if (n & 1) == 1:
                    ret = multiply(ret, mat)
                n >>= 1
                mat = multiply(mat, mat)
            return ret

        res = matrixPow(mat, n)
        ans = sum(res[0])
        return ans % MOD

背包问题

1、零钱兑换

for i in range(amount + 1):
    for coin in coins:
        if i - coin >= 0:
            dp[i] = min(dp[i], 1 + dp[i - coin])

2、零钱兑换II （单序列完全背包，正向遍历，无放入顺序）

for coin in coins:
    for i in range(amount + 1):
        if i - coin >= 0:
            dp[i] = dp[i] + dp[i - coin]

3、买钢笔和铅笔的方案数

dp = [1] + (total) * [0]
for cost in (cost1, cost2):
    for i in range(1, total + 1):
        if i - cost >= 0:
            dp[i] += dp[i - cost]
return sum(dp)

该题最优的方法是使用乘法原理：

res = 0
for i in range(total // cost1 + 1):
    res += math.ceil((total-cost1 * i) // cost2 + 1)

3、组合总和Ⅳ （单序列完全背包，正向遍历，有放入顺序）

for i in range(target + 1):
    for num in nums:
        if i - num >= 0:
            dp[i] = dp[i] + dp[i - num]

4、一和零（双序列01背包，逆向遍历）

for s in strs:
    c0, c1 = s.count('0'), s.count('1')
    for i in reversed(range(c0, m + 1)):
        for j in reversed(range(c1, n + 1)):
            dp[i][j] = max(dp[i][j], dp[i - c0][j - c1] + 1)

5、分割等和子集（单序列01背包）

for i in range(1, len(nums)):     
    for j in range(1, target + 1):
        dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]]

6、划分为k个相等的子集

size, n = 1 << len(nums), len(nums)
dp, s = [False] * size, [0] * size
dp[0] = True
for i in range(size):
    if not dp[i]: continue
    for j in range(n):
        if i & (1 << j) != 0:
            continue
        next_i = i | (1 << j)
        if dp[next_i]: continue
        if (s[i] % side) + nums[j] <= side:
            s[next_i] = s[i] + nums[j]
            dp[next_i] = True
        else: break
return dp[-1]

7、完全平方数

for i in range(1, n + 1):
    j = 1
    while j * j <= n:
        if i - j * j >= 0:
            dp[i] = min(dp[i - j * j] + 1, dp[i])
            j += 1
        else:
            break

8、目标和

for num in nums:
    for j in range((s + t) // 2, num - 1, -1):
        dp[j] += dp[j - num]

9、单词拆分

for i in range(len(s)):
    for word in wordDict:
        if s[i + 1 - len(word): i + 1] == word:
            dp[i + 1] = dp[i + 1] or dp[i + 1 - len(word)]

10、分汤（双序列完全背包，正向遍历）

for i in range(1, n + 1):
    for j in range(1, n + 1):
        dp[i][j] = 0.25 * (dp[max(i - 4, 0)][j] + dp[max(i - 3, 0)][j - 1] + 
        dp[max(i - 2, 0)][max(j - 2, 0)] + dp[i - 1][max(j - 3, 0)])

当维数过大，或者维数不确定时，使用自底向上动态规划容易造成维数灾难，例如：638. 大礼包，所以应该使用自顶向下的记忆化搜索的方法。

对于所给数据如果有一定特征，可以使用贪心的算法来优化，例如：和为 K 的最少斐波那契数字数目

路径动态规划

1、统计全为 1 的正方形子矩阵

for i in range(0, m):
    for j in range(0, n):
        if i == 0 or j == 0:
            dp[i][j] = matrix[i][j]
        elif matrix[i][j] == 1:
            dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
        c += dp[i][j]

2、最大正方形

for i in range(0, m):
    for j in range(0, n):
        if i == 0 or j == 0:
            dp[i][j] = int(matrix[i][j])
        elif matrix[i][j] == '1':
            dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
        max_c = max(max_c, dp[i][j])

3、三角形中最小路径之和

for i in range(1, len(triangle)):
    for j in range(len(triangle[i])):
        if j == 0:
            triangle[i][j] = triangle[i -1][0] + triangle[i][j]
        elif j == len(triangle[i]) - 1:
            triangle[i][j] = triangle[i -1][j - 1] + triangle[i][j]
        else:
            triangle[i][j] = min(triangle[i -1][j - 1], triangle[i -1][j]) + triangle[i][j]

4、最小路径和

for i in range(len(grid)):
    for j in range(len(grid[i])):
        if i == 0 and j > 0:
            dp[j] = dp[j - 1] + grid[i][j]
        elif j == 0 and i > 0:
            dp[j] = dp[j] + grid[i][j]
        elif j > 0 and  i > 0:
            dp[j] = min(dp[j - 1] + grid[i][j], dp[j] + grid[i][j])

5、不同路径 II

for i in range(0, m):
    for j in range(0, n):
        if obstacleGrid[i][j] == 1:
            dp[j] = 0
        elif i > 0 and j > 0:
            dp[j] = dp[j] + dp[j - 1]
        elif j > 0 and i == 0:
            dp[j] = dp[j - 1]

6、地下城游戏（不同路径的逆向遍历）

m, n = len(dungeon), len(dungeon[0])
dp = [[[0, 0] for _ in range(n)] for _ in range(m)]
for i, j in product(reversed(range(m)), reversed(range(n))):
    if i == m - 1 and j == n - 1:
        dp[i][j] = min(0, dungeon[i][j])
    elif i == m - 1:
        dp[i][j] = min(0, dp[i][j + 1] + dungeon[i][j])
    elif j == n - 1:
        dp[i][j] = min(0, dp[i + 1][j] + dungeon[i][j])
    else:
        dp[i][j] = min(0, max(dp[i][j + 1], dp[i + 1][j]) + dungeon[i][j]) 
return -dp[0][0] + 1

7、01 矩阵

for i in range(m):
    for j in range(n):
        if mat[i][j] == 0:
            dist[i][j] = 0
        if i > 0:
            dist[i][j] = min(dist[i][j], dist[i - 1][j] + 1)
        if j > 0:
            dist[i][j] = min(dist[i][j], dist[i][j - 1] + 1)
for i in range(m - 1, -1, -1):
    for j in range(n - 1, -1, -1):
        if i < m - 1:
            dist[i][j] = min(dist[i][j], dist[i + 1][j] + 1)
        if j < n - 1:
            dist[i][j] = min(dist[i][j], dist[i][j + 1] + 1)

8、统计农场中肥沃金字塔的数目

for i in range(m):
    for j in range(n):
        if grid[i][j] == 1:
            if j == 0 or j == n - 1:
                dp[i][j] = 1
            else:
                dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + 1
        else:
            dp[i][j] = 0

9、出界的路径数

for k in range(maxMove):
    for i in range(m):
        for j in range(n):
            if k == 0:
                dp[i][j][k] += 1 if i - 1 < 0 else 0
                dp[i][j][k]+= 1 if i + 1 >= m else 0
                dp[i][j][k]+= 1 if j - 1 < 0 else 0
                dp[i][j][k] += 1 if j + 1 >= n else 0
            else:
                dp[i][j][k] += dp[i - 1][j][k - 1] if i > 0 else 0
                dp[i][j][k] += dp[i + 1][j][k - 1] if i + 1 < m else 0
                dp[i][j][k] += dp[i][j - 1][k - 1] if j > 0 else 0
                dp[i][j][k] += dp[i][j + 1][k - 1] if j + 1 < n else 0
return sum(dp[startRow][startColumn])

10、矩阵中最长的连续1线段

m, n = len(mat), len(mat[0])
#用dp[i][j][k]记录，k分别表示水平、垂直、对角、反对角四个状态
dp = [[[0]*4 for _ in range(n+2)] for _ in range(m+2)]
ans = 0
for i in range(1, m+1):
    for j in range(1, n+1):
        if mat[i-1][j-1] == 1:
            dp[i][j][0] = dp[i-1][j][0] + 1
            dp[i][j][1] = dp[i][j-1][1] + 1
            dp[i][j][2] = dp[i-1][j-1][2] + 1
            dp[i][j][3] = dp[i-1][j+1][3] + 1
            ans = max(ans, max(dp[i][j]))
return ans

11、K 站中转内最便宜的航班

dp = [float('inf') for _ in range(n)]
dp[src] = 0
for i in range(K+1):
    tmp = dp[:]
    for u, v, w in flights:
        dp[v] = min(dp[v],tmp[u] + w)
return dp[dst] if dp[dst] != float('inf') else -1

也可以使用堆的方法进行遍历

graph = collections.defaultdict(dict)
for start,end,cost in flights:
    graph[start][end] = cost

queue, v = [(0,0,src)], set()
while queue:
    cost, k, pos = heapq.heappop(queue)
    if pos == dst: return cost
    if (pos, k) in v: continue
    v.add((pos, k))
    if k > K: continue
    for nxpos, nxcost in graph[pos].items():
        if (nxpos, k + 1) not in v:
            heapq.heappush(queue,(cost + nxcost, k + 1, nxpos))
return -1

12、网格图中递增路径的数目

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [[1 for i in range(n)] for j in range(m)]
        s = []
        mod = 10 ** 9 + 7
        for i in range(m):
            for j in range(n):
                s.append([grid[i][j], i, j])
        s.sort()
        while s:
            _, i, j = s.pop()#从尾部弹出则是从大到小遍历
            for x, y in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
                if 0 <= x < m and 0 <= y < n and grid[x][y] > _:
                    dp[i][j] += dp[x][y]
            dp[i][j] %= mod
        return sum(sum(i) for i in dp) % mod

使用记忆化深搜会更简单：

class Solution:
    def countPaths(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        @cache
        def dfs(i, j):
            res = 1
            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                ni, nj = i + dx, j + dy
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] > grid[i][j]:
                    res = (res + dfs(ni, nj)) % (10 ** 9 + 7)
            return res
        res = 0
        for i, j in product(range(m), range(n)):
            res = (res + dfs(i, j)) % (10 ** 9 + 7)
        return res

注：有些问题只适合于记忆化深搜，例如：将整数按权重排序，如果利用dp的方法，如果要通过所有测试用例，dp长度至少为300 * 最高值 + 3，而且运行时间远大于记忆化深搜。

决策动态规划

1、买卖股票的最佳时机 IV

# dp[i][kk][0]表示第i天第k笔交易不持有股票, dp[i][kk][1]表示第i天第k笔交易持有股票
for i in range(1, n):
    for kk in range(1, k + 1):
        dp[i][kk][0] = max(dp[i-1][kk][0], dp[i-1][kk][1] + prices[i])
        dp[i][kk][1] = max(dp[i-1][kk][1], dp[i-1][kk-1][0] - prices[i])
return dp[n-1][k][0]

2、将字符串翻转到单调递增

#a0最后一位为0最少需要翻转次数，a1最后一位为1最少需要翻转次数
for c in s:
    if c == '0':
        a1 = min(a0, a1) + 1
    else:
        a1 = min(a0, a1)
        a0 = a0 + 1

3、乘积最大子数组

maxF, minF, ans = nums[0], nums[0], nums[0]
length = len(nums)
for i in range(1, length):
    mx, mn = maxF, minF # 只用两个变量来维护i−1时刻的状态,优化空间
    maxF = max(mx * nums[i], nums[i], mn * nums[i])
    minF = min(mn * nums[i], nums[i], mx * nums[i])
    ans = max(maxF, ans)      
return ans

4、乘积为正数的最长子数组长度

class Solution:
    def getMaxLen(self, nums: List[int]) -> int:
        length = len(nums)
        positive, negative = [0] * length, [0] * length
        if nums[0] > 0:
            positive[0] = 1
        elif nums[0] < 0:
            negative[0] = 1
        
        maxLength = positive[0]
        for i in range(1, length):
            if nums[i] > 0:
                positive[i] = positive[i - 1] + 1
                negative[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)
            elif nums[i] < 0:
                positive[i] = (negative[i - 1] + 1 if negative[i - 1] > 0 else 0)
                negative[i] = positive[i - 1] + 1
            else:
                positive[i] = negative[i] = 0
            maxLength = max(maxLength, positive[i])

        return maxLength

该题还可以使用贪心的方法进行处理，按零分组，找第一个负数和最后一个负数的位置

5、丑数 II

dp = (n + 1) * [0]
n2, n3, n5 = 1, 1, 1
dp[1] = 1
for i in range(2, n + 1):
     dp[i] = min(2 * dp[n2], 3 * dp[n3], 5 * dp[n5])
     if dp[i] == 2 * dp[n2]: n2 += 1
     if dp[i] == 3 * dp[n3]: n3 += 1
     if dp[i] == 5 * dp[n5]: n5 += 1
return dp[n]

6、优美的排列

f = [0] * (1 << n)
f[0] = 1
for mask in range(1, 1 << n):
    num = bin(mask).count("1")
    for i in range(n):
        if mask & (1 << i) and (num % (i + 1) == 0 or (i + 1) % num == 0):
            f[mask] += f[mask ^ (1 << i)]
return f[(1 << n) - 1]

7、只有两个键的键盘

if n == 1: return 0
dp = [[inf] * (n // 2 + 1) for _ in range(n + 1)]
dp[1][0], dp[1][1] = 0, 1
for i in range(2, n + 1):
    for k in range(1, i // 2 + 1):
        if i - k >= 0:
            dp[i][k] = min(dp[i][k], dp[i - k][k] + 1)
        if k == i // 2 and i % 2 == 0:
            dp[i][k] = min(dp[i][k], min(dp[k]) + 2)
return min(dp[-1])

由于一个素数的字母的最小操作次数是其本身，所以可以转化为如下动态规划算法：

f = [0] * (n + 1)
for i in range(2, n + 1):
    f[i] = float("inf")
    j = 1
    while j * j <= i:
        if i % j == 0:
            f[i] = min(f[i], f[j] + i // j)
            f[i] = min(f[i], f[i // j] + j)
        j += 1
return f[n]

由于两个素数的和小于其乘积，所以可优化成采用分解质因数的方法

8、新 21 点（前缀和 + 动态规划）

dp = [1] + [0] * n
for i in range(1, n + 1):
    if i <= n - k:
        dp[i] = dp[i - 1] + 1
        continue
    dp[i] = dp[i - 1] - (dp[i - maxPts - 1] if i - maxPts > 0 else 0)
    dp[i] = dp[i - 1] + dp[i] / maxPts
return dp[-1] - (dp[-2] if n >= 1 else 0)

9、计算分配糖果的不同方式（斯特林数）

for i in range(1, k + 1):       #盒子
	for j in range(i + 1, n + 1):   #糖果数
		#新的糖果，单独一个盒子
		dp[i][j] = dp[i-1][j-1]
		#新的糖果，加入其他的盒子
		dp[i][j] += dp[i][j-1] * i

10、石子游戏 II（前缀和 + 动态规划）

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        pre = [0]
        for p in piles:
            pre.append(pre[-1] + p)
        
        n = len(piles)
        @cache
        def dfs(i, M):
            if i + 2 * M >= n:
                return pre[-1] - pre[i]
            maxl = 0
            for j in range(1, 2 * M + 1):
                maxl = max(maxl, pre[-1] - pre[i] - dfs(j + i, max(M, j)))
            return maxl
        
        return dfs(0, 1)

动态规划与树结合

1、打家劫舍 III

class Solution:
    def rob(self, root: TreeNode) -> int:
        def dfs(p):
            if not p: return 0, 0
            la, lb = dfs(p.left)
            ra, rb = dfs(p.right)
            return max(lb + rb + p.val, ra + la), ra + la
        return max(dfs(root))

2、二叉树中的最长交错路径

class Solution:
    def longestZigZag(self, root: TreeNode) -> int:
        maxl = 0
        def dfs(p):
            nonlocal maxl
            if not p: return -1, -1
            l1, r1 = dfs(p.left)
            l2, r2 = dfs(p.right)
            maxl = max(maxl, r1 + 1, l2 + 1)
            return r1 + 1, l2 + 1
        dfs(root)
        return maxl

3、二叉搜索子树的最大键值和

class Solution:
    def maxSumBST(self, root: Optional[TreeNode]) -> int:
        maxl = 0
        def dfs(p):          
            min1, max1, s1 = dfs(p.left) if p.left else (inf, -inf, 0)
            min2, max2, s2 = dfs(p.right) if p.right else (inf, -inf, 0)
            if max1 < p.val < min2:
                nonlocal maxl
                maxl = max(maxl, s1 + s2 + p.val)
                return min(min1, p.val), max(max2, p.val), s1 + s2 + p.val
            return -inf, inf, 0
        dfs(root)
        return maxl

4、统计可能的树根数目（换根dp）

（1）先从任意一个根出发，求解所有点

（2）再换根，计算变化的点

class Solution:
    def rootCount(self, edges: List[List[int]], guesses: List[List[int]], k: int) -> int:
        m = defaultdict(list)
        for f, t in edges:
            m[f].append(t)
            m[t].append(f)
        
        s = defaultdict(int)
        for f, t in guesses:
            s[f, t] += 1
            
        t = 0
        def dfs(i, last):
            nonlocal t
            for j in m[i]:
                if j == last: continue
                t += s[i, j] 
                dfs(j, i)
        
        dfs(0, -1)
        res = 0
        def dfs2(i, last, t):
            nonlocal res
            if t >= k: res += 1
            for j in m[i]:
                if j == last: continue
                dfs2(j, i, t - s[i, j] + s[j, i])
                
        dfs2(0, -1, t)
        return res

5、树中距离之和（换根dp）

class Solution:
    def sumOfDistancesInTree(self, n: int, edges: List[List[int]]) -> List[int]:
        m = defaultdict(list)
        for f, t in edges:
            m[f].append(t)
            m[t].append(f)
        
        dises, sizes  = [0] * n, [0] * n
        #节点到所有孩子节点的距离，以及节点与所有孩子节点的个数
        def dfs(i, last):
            dis, size = 0, 1
            for j in m[i]:
                if j == last: continue
                child_dis, child_size = dfs(j, i)
                dis += child_dis + child_size
                size += child_size
            dises[i], sizes[i] = dis, size
            return dis, size

        dfs(0, -1)

        res = [0] * n
        res[0] = dises[0]
        def dfs2(i, last, dis, size):      
            sum_child_size, sum_child_dis = 0, 0
            for j in m[i]:
                if j == last: continue
                sum_child_size += sizes[j]
                sum_child_dis += dises[j]
            
            for j in m[i]:
                if j == last: continue
                parent_dis = dis + 2 * (sum_child_size - sizes[j]) + sum_child_dis - dises[j] + size
                parent_size = size + sum_child_size - sizes[j] + 1
                res[j] = parent_dis + dises[j]
                dfs2(j, i,  parent_dis, parent_size)
        
        dfs2(0, -1, 0, 1)

        return res

数位动态规划

1、至少有 1 位重复的数字

class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        s = str(n)
        @cache
        def f(i: int, mask: int, is_limit: bool, is_num: bool) -> int:
            if i == len(s):
                return int(is_num)
            res = 0
            if not is_num:  # 可以跳过当前数位
                res = f(i + 1, mask, False, False)
            up = int(s[i]) if is_limit else 9
            for d in range(0 if is_num else 1, up + 1):  # 枚举要填入的数字 d
                if mask >> d & 1 == 0:  # d 不在 mask 中
                    res += f(i + 1, mask | (1 << d), is_limit and d == up, True)
            return res
        return n - f(0, 0, True, False)

2、不含连续1的非负整数

class Solution:
    def findIntegers(self, n: int) -> int:
        s = str(bin(n))[2:]
        @cache
        def f(i: int, pre1: bool, is_limit: bool) -> int:
            if i == len(s):
                return 1
            up = int(s[i]) if is_limit else 1
            res = f(i + 1, False, is_limit and up == 0)  # 填 0
            if not pre1 and up == 1:  # 可以填 1
                res += f(i + 1, True, is_limit)  # 填 1
            return res
        return f(0, False, True)

倍增

1、Pow(x, n) -- 快速幂算法

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n == 0: return 1
        n, f = abs(n), (n < 0)
        p = [x] * n.bit_length()
        for i in range(n.bit_length() - 1):
            p[i + 1] = p[i] * p[i]
        res = 1
        for i in range(n.bit_length()):
            if (n >> i) & 1:
                res *= p[i]
        if f: return 1 / res
        return res

2、在传球游戏中最大化函数值 -- (求解第k个祖先)

class Solution:
    def getMaxFunctionValue(self, receiver: List[int], k: int) -> int:
        n = len(receiver)
        m = k.bit_length() - 1
        pa = [[(p, p)] + [None] * m for p in receiver]
        for i in range(m):
            for x in range(n):
                p, s = pa[x][i]
                pp, ss = pa[p][i]
                pa[x][i + 1] = (pp, s + ss)  # 合并节点值之和

        ans = 0
        for i in range(n):
            x = sum = i
            for j in range(m + 1):
                if (k >> j) & 1:  # k 的二进制从低到高第 j 位是 1
                    x, s = pa[x][j]
                    sum += s
            ans = max(ans, sum)
        return ans

状态压缩与优化

1、取余法：（70. 爬楼梯）

dp = [1, 2] 
for i in range(2, n):
    dp[i % 2] = dp [(i -1) % 2] + dp[(i - 2) % 2]
return dp[(n - 1) % 2]

2、常数级别压缩：（70. 爬楼梯）

a, b = 0, 1
for i in range(n):
    a, b = b, a + b
return b

3、二维压缩成一维：（72. 编辑距离）

s, t = (word1, word2) if len(word1) > len(word2) else (word2, word1)
dp = [j for j in range(len(t) + 1)]
for i in range(1, len(s)+1):
    dpij, dp[0] = dp[0], i
    for j in range(1, len(t) + 1):
        temp = dp[j]
        if s[i - 1] == t[j - 1]:
            dp[j] = dpij
        else:
            dp[j] = min(dp[j] + 1, dp[j - 1] + 1, dpij + 1)
        dpij = temp
return dp[-1]

4、使用位运算进行压缩：（2510. Check if There is a Path With Equal Number of 0's And 1's）

常规方法，使用集合存储结果，运行时间为376ms，内存消耗146.8mb，代码如下：

class Solution:
    def isThereAPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        @cache
        def dfs(i, j):
            if i <= 0 and j < 0 or i < 0 and j <= 0: return {0}
            if i < 0 or j < 0: return set()
            res = set()
            for e in dfs(i - 1, j) | dfs(i, j - 1):
                if grid[i][j]:
                    res.add(e + 1)
                else:
                    res.add(e - 1)
            return res
           
        return 0 in dfs(m - 1, n - 1)

如果使用位运算存储结果，运行时间为60ms，内存消耗22.2mb，代码如下：

class Solution:
    def isThereAPath(self, grid: List[List[int]]) -> bool:
        m, n = len(grid), len(grid[0])
        @cache
        def dfs(i, j):
            if i <= 0 and j < 0 or i < 0 and j <= 0: return 1 << (m + n)
            if i < 0 or j < 0: return 0
            if grid[i][j]:
                return (dfs(i - 1, j) << 1) | (dfs(i, j - 1) << 1)
            else:
                return (dfs(i - 1, j) >> 1) | (dfs(i, j - 1) >> 1)

        return ((dfs(m - 1, n - 1) >> (m + n)) & 1) == 1

进阶方法：具有哈希功能位运算压缩 -- 得到新鲜甜甜圈的最多组数

常规方法，使用最多10维状态空间，代码如下，运行时间为4662ms，内存占用236.5mb

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        mp = defaultdict(int)
        for g in groups:
            mp[g % batchSize] += 1

        @cache
        def dfs(s, *b):
            if sum(b) == len(groups):
                return 0
            res, t = 0, (1 if s % batchSize == 0 else 0) 
            for j in range(len(b)):
                if b[j] >= mp[j]: continue
                bb = list(b)
                bb[j] += 1
                res = max(res, dfs((s + j) % batchSize, *bb) + t)
            return res

        return dfs(0, *([0] * batchSize))

使用具有哈希功能的位运算压缩，每个数字分配5bit，值最高为31，代码如下，运行时间为1665ms，占用内存43.8mb

class Solution:
    def maxHappyGroups(self, batchSize: int, groups: List[int]) -> int:
        kWidth = 5
        kWidthMask = (1 << kWidth) - 1

        cnt = Counter(x % batchSize for x in groups)

        start = 0
        for i in range(batchSize - 1, 0, -1):
            start = (start << kWidth) | cnt[i]

        @cache
        def dfs(mask: int) -> int:
            if mask == 0:
                return 0

            total = 0
            for i in range(1, batchSize):
                amount = ((mask >> ((i - 1) * kWidth)) & kWidthMask)
                total += i * amount

            best = 0
            for i in range(1, batchSize):
                amount = ((mask >> ((i - 1) * kWidth)) & kWidthMask)
                if amount > 0:
                    result = dfs(mask - (1 << ((i - 1) * kWidth)))
                    if (total - i) % batchSize == 0:
                        result += 1
                    best = max(best, result)

            return best

        ans = dfs(start) + cnt[0]
        dfs.cache_clear()
        return ans

01背包问题bitset优化 -- 执行操作可获得的最大总奖励 II

代码如下：

class Solution:
    def maxTotalReward(self, rewardValues: List[int]) -> int:
        f = 1
        for v in sorted(set(rewardValues)):
            f |= (f & ((1 << v) - 1)) << v
        return f.bit_length() - 1

5、使用26个字母空间

（1）2370. 最长理想子序列：

f = [0] * 26
for c in s:
    c = ord(c) - ord('a')
    f[c] = 1 + max(f[max(c - k, 0): c + k + 1])
return max(f)

（2）不同的子序列 II

对于相同的子序列，只会考虑其最后一次出现的位置（下标序列的字典序最大）

class Solution:
    def distinctSubseqII(self, s: str) -> int:
        mod = 10 ** 9 + 7
        dp = [0] * 26
        for c in s:
            i = ord(c) - ord('a')
            for j in range(26):
                if i == j: continue
                dp[i] = (dp[j] + dp[i]) % mod
            dp[i] = (dp[i] + 1) % mod
        return sum(dp) % mod

6、使用线段树（2407. 最长递增子序列 II）

class Solution:
    def lengthOfLIS(self, nums: List[int], k: int) -> int:
        tmp = SegmentTree([0] * (max(nums) + 1))
        for x in nums:
            note = tmp.query(max(0, x-k), x-1)
            tmp.update(x, note + 1)
        return tmp.query(0, max(nums))
        
class SegmentTree:
    def __init__(self, data, merge=max): 
        self.data = data
        self.n = len(data)
        self.tree = [None] * (4 * self.n)
        self._merge = merge
        if self.n:
            self._build(0, 0, self.n-1)


    def query(self, ql, qr):
        return self._query(0, 0, self.n-1, ql, qr)

    def update(self, index, value):
        self.data[index] = value
        self._update(0, 0, self.n-1, index)

    def _build(self, tree_index, l, r):
        if l == r:
            self.tree[tree_index] = self.data[l]
            return
        mid = (l+r) // 2
        left, right = 2 * tree_index + 1, 2 * tree_index + 2
        self._build(left, l, mid)
        self._build(right, mid+1, r)
        self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])

    def _query(self, tree_index, l, r, ql, qr):
        if l == ql and r == qr:
            return self.tree[tree_index]

        mid = (l+r) // 2
        left, right = tree_index * 2 + 1, tree_index * 2 + 2
        if qr <= mid:
            return self._query(left, l, mid, ql, qr)
        elif ql > mid:
            return self._query(right, mid+1, r, ql, qr)

        return self._merge(self._query(left, l, mid, ql, mid), 
                          self._query(right, mid+1, r, mid+1, qr))

    def _update(self, tree_index, l, r, index):
        if l == r == index:
            self.tree[tree_index] = self.data[index]
            return
        mid = (l+r)//2
        left, right = 2 * tree_index + 1, 2 * tree_index + 2
        if index > mid:
            self._update(right, mid+1, r, index)
        else:
            self._update(left, l, mid, index)
        self.tree[tree_index] = self._merge(self.tree[left], self.tree[right])

进阶：利用线段树的分治思想改造递推关系 -- 不包含相邻元素的子序列的最大和

代码如下：

class Solution:
    def maximumSumSubsequence(self, nums: List[int], queries: List[List[int]]) -> int:
        n = len(nums)
        # 4 个数分别保存 f00, f01, f10, f11
        t = [[0] * 4 for _ in range(2 << n.bit_length())]

        def maintain(o: int):
            a, b = t[o * 2], t[o * 2 + 1]
            t[o][0] = max(a[0] + b[2], a[1] + b[0])
            t[o][1] = max(a[0] + b[3], a[1] + b[1])
            t[o][2] = max(a[2] + b[2], a[3] + b[0])
            t[o][3] = max(a[2] + b[3], a[3] + b[1])

        # 用 nums 初始化线段树
        def build(o: int, l: int, r: int) -> None:
            if l == r:
                t[o][3] = max(nums[l], 0)
                return
            m = (l + r) // 2
            build(o * 2, l, m)
            build(o * 2 + 1, m + 1, r)
            maintain(o)

        # 把 nums[i] 改成 val
        def update(o: int, l: int, r: int, i: int, val: int) -> None:
            if l == r:
                t[o][3] = max(val, 0)
                return
            m = (l + r) // 2
            if i <= m:
                update(o * 2, l, m, i, val)
            else:
                update(o * 2 + 1, m + 1, r, i, val)
            maintain(o)

        build(1, 0, n - 1)
        ans = 0
        for i, x in queries:
            update(1, 0, n - 1, i, x)
            ans += t[1][3]  # 注意 f11 没有任何限制，也就是整个数组的打家劫舍
        return ans % 1_000_000_007

7、提高状态空间的重用性

（1）2143.在两个数组的区间中选取数字中，如下方法设置状态空间运行结果为超时

class Solution:
    def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        @cache
        def dfs(i, l, is_start, r, is_end):
            if i == n: 
                return int(l == r) if is_start else 0
            res = 0
            if not is_start:
                res += dfs(i + 1, l, False, r, False)
                res += dfs(i + 1, l + nums1[i], True, r , False)
                res += dfs(i + 1, l, True, r + nums2[i], False)              
            elif is_start and not is_end:
                res += dfs(i + 1, l + nums1[i], True, r , False)
                res += dfs(i + 1, l, True, r + nums2[i], False)
                res += dfs(i + 1, l, True, r, True)
            else:
                res += dfs(i + 1, l, True, r, True)
            return res
        return dfs(0, 0, False, 0, False)

这是因为(l, r) == (1, 1) 与 (l, r) == (6, 6)的状态是等价的，但是状态空间没有复用，导致重复计算，所以可以按如下方法改正，状态空间优化成一个，结果通过：

class Solution:
    def countSubranges(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)
        @cache
        def dfs(i, d, is_start, is_end):
            if i == n: return int(d == 0) if is_start else 0
            if is_end: return int(d == 0)
            res = 0
            if not is_start:
                res += dfs(i + 1, d, False, False)
                res += dfs(i + 1, d + nums1[i], True, False)
                res += dfs(i + 1, d - nums2[i], True, False)              
            elif is_start and not is_end:
                res += dfs(i + 1, d + nums1[i], True, False)
                res += dfs(i + 1, d - nums2[i], True, False)
                res += dfs(i + 1, d, True, True)
            else:
                res += dfs(i + 1, d, True, True)
            return res
        return dfs(0, 0, False, False) % (10 ** 9 + 7)

类似的还有 956. 最高的广告牌，题解可参考：. - 力扣（LeetCode）

（2）在盈利计划中，如下方法超时：

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:    
        mod = 10 ** 9 + 7
        @cache
        def dfs(i, n, p):
            if i == len(group):
                return p >= minProfit
            res = 0
            if group[i] <= n:
                res = (res + dfs(i + 1, n - group[i], p + profit[i])) % mod
            return (res + dfs(i + 1, n, p)) % mod
        
        return dfs(0, n, 0) % mod

这是由于当前盈利值达到最低要求后，后续结果只与剩余人数有关，所以按照最小盈利值对状态进行重用，如下所示。

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:    
        mod = 10 ** 9 + 7
        @cache
        def dfs(i, n, p):
            if i == len(group):
                return int(p == minProfit)
            res = 0
            if group[i] <= n:
                res = (res + dfs(i + 1, n - group[i], min(minProfit, p + profit[i]))) % mod
            return (res + dfs(i + 1, n, p)) % mod
        
        return dfs(0, n, 0) % mod

8、缩短计算步数

（1） Minimum Time to Kill All Monsters

如下解法运行超时，因为当怪物需要的能量比较大时，计算次数变多。

class Solution:
    def minimumTime(self, power: List[int]) -> int:
        n, mp = len(power), max(power)
        @cache
        def dfs(g, v, inc):
            if v == (1 << n) - 1: return 0
            res, gg, step = inf, g - inc, 0
            while gg <= mp:
                gg += inc
                step += 1
                for i in range(n):
                    if (v >> i) & 1 == 0 and gg >= power[i]:
                        res = min(res, dfs(inc + 1, v | (1 << i), inc + 1) + step)
            return res
        return dfs(1, 0, 1)

根据题意，结果只与打败怪物的顺序有关，与积攒能量的过程无关，所以可以优化成下面的方法，减少重复计算，同时优化状态空间。

class Solution:
    def minimumTime(self, power: List[int]) -> int:
        n, mp = len(power), max(power)
        @cache
        def dfs(v, inc):
            if v == (1 << n) - 1: return 0
            res = inf
            for i in range(n):
                if (v >> i) & 1 == 0:
                    res = min(res, dfs(v | (1 << i), inc + 1) + ceil(power[i] / inc))
            return res
        return dfs(0, 1)

（2）好二进制字符串的数量

根据题意设计如下代码，会超时：

class Solution:
    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:
        @cache
        def dfs(i, p):
            res = 0
            if minLength <= i <= maxLength and p == 0:
                res = 1
            if i == maxLength: return res
            if p <= 0:
                res += dfs(i + 1, -((-p + 1) % zeroGroup))
            if p >= 0:
                res += dfs(i + 1, (p + 1) % oneGroup)
            return res % (10 ** 9 + 7)
        return dfs(0, 0) % (10 ** 9 + 7)

由于要求具有连续相同字符，所以不需要计算使用每个字符的状态，如下所示，通过减少状态空间和缩短步数来达到优化的目的。

class Solution:
    def goodBinaryStrings(self, minLength: int, maxLength: int, oneGroup: int, zeroGroup: int) -> int:
        @cache
        def dfs(i):
            res = 0
            if minLength <= i <= maxLength:
                res = 1
            if i == maxLength: return res
            if i + oneGroup <= maxLength:
                res += dfs(i + oneGroup)
            if i + zeroGroup <= maxLength:
                res += dfs(i + zeroGroup)
            return res % (10 ** 9 + 7)
        return dfs(0) % (10 ** 9 + 7)

（3）吃掉 N 个橘子的最少天数

直接使用暴力dp超时，因为n最大超过10^9, 每次减一需要的时间比较长，所以可以对减一部分进行优化，由于n 变为二分之一或者三分之一步数总是比连续减一的步数小，所以可以写成如下代码：

class Solution:
    @lru_cache(None) 
    def minDays(self, n: int) -> int:
        if n == 0: return 0
        if n == 1: return 1
        return 1 + min(self.minDays(n//2) + n % 2, self.minDays(n//3) + n % 3)

9、剪枝法

（1）出租车的最大盈利

如下使用动态规划的方法，会超时

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides.sort()
        @cache
        def dfs(j):            
            idx = bisect_left(rides, [j, 0, 0])
            if idx >= len(rides): return 0
            maxl = 0
            for i in range(idx, len(rides)):
                start, end, tip = rides[i]
                maxl = max(maxl, dfs(end) + end - start + tip)
            return maxl
        return dfs(0)

这是因为当两个区间不相交时，两个区间都取到时收益最大，所以在新的起始点大于最小终止点时，结束计算，如下所示：

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides.sort()
        @cache
        def dfs(j):            
            idx = bisect_left(rides, [j, 0, 0])
            if idx >= len(rides): return 0
            maxl = 0
            s0, e0, t0 = rides[idx]
            for i in range(idx, len(rides)):
                start, end, tip = rides[i]
                e0 = min(e0, end)
                if start >= e0: break
                maxl = max(maxl, dfs(end) + end - start + tip)
            return maxl
        return dfs(0)

也可以利用区间结束点的顺序和二分查找法对其进行优化：

class Solution:
    def maxTaxiEarnings(self, n: int, rides: List[List[int]]) -> int:
        rides = sorted(rides, key=lambda x: x[1])
        dp = [[0, 0]]
        for s, e, p in rides:
            i = bisect.bisect(dp, [s + 1]) - 1
            if dp[i][1] +  p + e - s > dp[-1][1]:
                dp.append([e, dp[i][1] + p + e - s])
        return dp[-1][1]

（2）石子游戏 V

常规的dp导致超时，根据等比数列求和公式可知，能预估后续得分之和，当小于当前最大值时可以剪枝，代码如下：

class Solution:
    def stoneGameV(self, stoneValue: List[int]) -> int:
        pre = [0]
        for v in stoneValue:
            pre.append(pre[-1] + v)
        
        @cache
        def dfs(i, j):
            if i == j: return 0
            maxl = 0
            for k in range(i, j):
                left = pre[k + 1] - pre[i]
                right = pre[j + 1] - pre[k + 1]
                if left < right:
                    if maxl >= 2 * left: continue
                    maxl = max(maxl, dfs(i, k) + left)
                elif right < left:
                    if maxl >= 2 * right: continue
                    maxl = max(maxl, dfs(k + 1, j) + right)
                else:
                    if maxl >= 2 * right: continue
                    maxl = max(maxl, dfs(i, k) + left, dfs(k + 1, j) + right)
            return maxl
        return dfs(0, len(stoneValue) - 1)

（3）收集所有金币可获得的最大积分

由于每个节点的金币数量最高为10^4，所以当除数大于2^13时金币数为0，可以不用继续往下进行。

class Solution:
    def maximumPoints(self, edges: List[List[int]], coins: List[int], k: int) -> int:
        m = defaultdict(set)
        for f, t in edges:
            m[f].add(t)
            m[t].add(f)
        
        def dfs(p, last):
            for np in list(m[p]):
                if np == last:
                    m[p].remove(np)
                    continue
                dfs(np, p)
        dfs(0, -1)

        @cache
        def dp(p, mm):
            r1 = coins[p] // mm - k
            r2 = coins[p] // mm // 2
            for np in m[p]:        
                if r1 < r2 and mm < 2 ** 13:
                    r2 += dp(np, 2 * mm)
                r1 += dp(np, mm)
            return max(r1, r2)
        
        return dp(0, 1)

（4）相似度为 K 的字符串

构造环+位掩码的算法，代码如下，运行时间为1381ms：

class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        ns1, ns2 = '', ''
        for i, c in enumerate(s1):
            if s1[i] == s2[i]: continue
            ns1 += s1[i]
            ns2 += s2[i]
        
        s1, s2 = ns1, ns2

        m = defaultdict(list)
        for i, c in enumerate(s1):
            m[c].append(i)
        n = len(s1)
        @cache
        def dfs(mask, head=-1, last=-1):
            if mask.bit_count() == n:
                return 0
            res = []
            if head == -1:
                for i in range(n):
                    if (mask >> i) & 1 == 1: continue
                    res.append(dfs(mask | (1 << i), s1[i], s2[i]))
            else:
                for j in m[last]:
                    if (mask >> j) & 1 == 1: continue
                    if s2[j] == head:
                        res.append(dfs(mask | (1 << j), -1, -1) - 1)
                    else:
                        res.append(dfs(mask | (1 << j), head, s2[j]))
            return min(res)

        return n + dfs(0, -1, -1)

环的每一点都是等价的，所以从未遍历一点进入即可。同时切分的环越多越好，当到达能够形成环的位置时终止，代码如下，运行时间为37ms

class Solution:
    def kSimilarity(self, s1: str, s2: str) -> int:
        m, t = defaultdict(list), 0
        mask = 0
        for i, c in enumerate(s1):
            if s1[i] == s2[i]: 
                mask = mask | (1 << i)
                continue
            m[c].append(i)
            t += 1
        n = len(s1)
        @cache
        def dfs(mask, head=-1, last=-1):
            if mask.bit_count() == n:
                return 0
            res = []
            if head == -1:
                for i in range(n):
                    if (mask >> i) & 1 == 1: continue
                    if s1[i] != s2[i]:
                        return dfs(mask | (1 << i), s1[i], s2[i])
            else:
                for j in m[last]:
                    if (mask >> j) & 1 == 1: continue
                    if s2[j] == head:
                        return dfs(mask | (1 << j), -1, -1) - 1
                    else:
                        res.append(dfs(mask | (1 << j), head, s2[j]))
            return min(res)

        return t + dfs(mask, -1, -1)

10、逆向思维求解 -- 好分区的数目

如果直接求解好分区数量，但是背包容量太大，会超时，代码如下：

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        sm = sum(nums)
        @cache
        def dfs(i, s):
            if i == len(nums):
                return 1 if sm - s >= k and s >= k else 0 
            return dfs(i + 1, s + nums[i]) + dfs(i + 1, s)
        return dfs(0, 0) % (10 ** 9 + 7)

可以通过求不好分区数量，再用总数相减来提高求解效率，即第一个组或第二个组的元素和小于 k的方案数。根据对称性，我们只需要计算第一个组的元素和小于 k 的方案数，然后乘 2即可：

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        sm = sum(nums)
        if sm < k * 2: return 0
        mod = (10 ** 9 + 7) 
        @cache
        def dfs(i, s):
            if i == len(nums): return 1 
            res = dfs(i + 1, s)
            if s >= nums[i]:
                res += dfs(i + 1, s - nums[i])
            return res % mod 
        return (pow(2, len(nums), mod) - dfs(0, k - 1) * 2) % mod

再转化成01背包的形式，进一步提高效率：

class Solution:
    def countPartitions(self, nums: List[int], k: int) -> int:
        if sum(nums) < k * 2: return 0
        MOD = 10 ** 9 + 7
        f = [0] * k
        f[0] = 1
        for x in nums:
            for j in range(k - 1, x - 1, -1):
                f[j] = (f[j] + f[j - x]) % MOD
        return (pow(2, len(nums), MOD) - sum(f) * 2) % MOD

11、问题转化

（1） K 次调整数组大小浪费的最小总空间

直接使用动态规划进行求解，会超时:

class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        n = len(nums)
        
        @cache
        def dfs(i, j, k):
            if i == len(nums): return 0
            if nums[i] <= nums[j]:
                minl = dfs(i + 1, j, k) + nums[j] - nums[i]
            else: minl = inf
            if k > 0:
                for jj in range(j + 1, n):
                    if nums[jj] >= nums[i]:
                        minl = min(minl, dfs(i + 1, jj, k - 1) + nums[jj] - nums[i])
            return minl
        
        return min(dfs(0, j, k) for j in range(n))

可以理解成将数组分成k + 1组，求每组最大值乘以这一段的长度再减去这一段的元素和，找到总体最小值，代码如下：

class Solution:
    def minSpaceWastedKResizing(self, nums: List[int], k: int) -> int:
        n = len(nums)
        pre = [0]
        for num in nums:
            pre.append(pre[-1] + num)

        @cache
        def diff(i, j):
            return (j - i + 1) * max(nums[i: j + 1]) -  pre[j + 1] + pre[i]

        @cache
        def dfs(i, j, k):
            minl = diff(i, j)
            if k > 0:
                for t in range(i, j):
                    minl = min(minl, dfs(i, t, k - 1) + diff(t + 1, j))

            return minl
        
        return dfs(0, n - 1, k)

（2）准时抵达会议现场的最小跳过休息次数

直接根据题意，使用距离为空间维度的动态规划超出内容，代码如下：

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        n = len(dist)
        @cache
        def dfs(i, d):
            if d > speed * hoursBefore: return inf
            if i == n: return 0
            if (d + dist[i]) % speed == 0 or i == n - 1:
                return dfs(i + 1, d + dist[i])
            res = dfs(i + 1, d + dist[i]) + 1
            res = min(res, dfs(i + 1, (d + dist[i]) // speed * speed + speed ))
            return res
        
        return dfs(0, 0) if dfs(0, 0) < inf else -1

可以转化成求最多跳转次数（j）的最短时间，找出时间符合要求的最小j，代码如下：

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        @cache
        def dfs(i, j):
            if i == 0: return 0
            d = dfs(i - 1, j) + dist[i - 1]
            if d % speed == 0 or i == len(dist): return d
            res = d + speed - d % speed
            if j > 0:
                res = min(res, dfs(i - 1, j - 1) + dist[i - 1])
            return res 
        
        for j in range(len(dist)):
            if dfs(len(dist), j) <= speed * hoursBefore: return j

        return  -1

12、降低参数维度

（1）减少不必要的参数 -- 两个子序列的最大点积

如下所示，如果用f来判别是否为空数组，运行时间为1148ms

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        @cache
        def dfs(i, j, f):
            if i == len(nums1) or j == len(nums2): return 0 if f else -inf
            return max(dfs(i + 1, j, f), dfs(i, j + 1, f), dfs(i + 1, j + 1, True) + nums1[i] * nums2[j])
        return dfs(0, 0, False)

可以改变max的判断来减少维度，运行时间为628ms

class Solution:
    def maxDotProduct(self, nums1: List[int], nums2: List[int]) -> int:
        @cache
        def dfs(i, j):
            if i == len(nums1) or j == len(nums2): return -inf
            return max(dfs(i + 1, j), dfs(i, j + 1), dfs(i + 1, j + 1) + nums1[i] * nums2[j], nums1[i] * nums2[j])
        return dfs(0, 0)

（2）将参数移至返回值 -- 完成任务的最少工作时间段

当任务已使用时间在函数参数时，运行时间为7092ms

class Solution:
    def minSessions(self, tasks: List[int], sessionTime: int) -> int:
        n = len(tasks)
        @cache
        def dfs(v, s):
            if v.bit_count() == n:
                return 0
            minl = inf
            for i in range(n):
                if (v >> i) & 1 == 1: continue
                if tasks[i] <= s:
                    minl = min(minl, dfs(v | (1 << i), s - tasks[i]))
                else:
                    minl = min(minl, dfs(v | (1 << i), sessionTime - tasks[i]) + 1)
            return minl
        return dfs(0, sessionTime) + 1

当任务已使用时间放到返回值时，运行时间为1196ms

class Solution:
    def minSessions(self, tasks: List[int], sessionTime: int) -> int:
        n = len(tasks)
        @cache
        def dfs(v):
            if v.bit_count() == n:
                return 1, 0
            minl, mins = inf, inf
            for i in range(n):
                if (v >> i) & 1 == 1: continue
                l, s = dfs(v | (1 << i))
                if tasks[i] + s <= sessionTime:
                    minl, mins = min((minl, mins), (l, s + tasks[i]))
                else:
                    minl, mins = min((minl, mins), (l + 1, tasks[i]))
            return minl, mins
        return dfs(0)[0]

（3）执行操作使两个字符串相等

根据题意，使用动态规划进行求解，代码如下，用时368ms

class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        if abs(s1.count('1') - s2.count('1')) & 1 == 1:
            return -1
        @cache
        def dfs(i, t, is_prev):
            if i == len(s1):
                return inf if t > 0 or is_prev else 0
            if (s1[i] == s2[i]) == (not is_prev):
                return dfs(i + 1, t, False)
            
            minl = min(dfs(i + 1, t + 1, False) + x, dfs(i + 1, t, True) + 1)
            if t > 0:
                minl = min(minl, dfs(i + 1, t - 1, False))

            return minl

        return dfs(0, 0, False)

可以证明不同字符之间只能有一次操作，所以可以在不同字符下标处进行转移，缩短计算步数。

代码如下，运行时间为43ms：

class Solution:
    def minOperations(self, s1: str, s2: str, x: int) -> int:
        if s1 == s2:
            return 0
        p = [i for i, (x, y) in enumerate(zip(s1, s2)) if x != y]

        if len(p) % 2:
            return -1
        f0, f1 = 0, x
        for i, j in pairwise(p):
            f0, f1 = f1, min(f1 + x, f0 + (j - i) * 2)
        return f1 // 2

（4）从底到上递推，巧用返回值 -- 可处理的最大删除操作数 I

该题直接使用三维空间遍历超出内存，使用自底向上的递推方法能根据返回值得知查询顺序，从而节省一维空间，代码如下：

class Solution:
    def maximumProcessableQueries(self, nums: List[int], queries: List[int]) -> int:
        n = len(nums)
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for delta in range(n - 1, -1, -1):
            for j in range(delta, n + 1):
                i = j - delta
                if i > 0:
                    if dp[i - 1][j] < len(queries) and nums[i - 1] >= queries[dp[i - 1][j]]:
                        dp[i][j] = dp[i - 1][j] + 1
                    else:
                        dp[i][j] = dp[i - 1][j]
                if j < len(nums):
                    if dp[i][j + 1] < len(queries) and nums[j] >= queries[dp[i][j + 1]]:
                        dp[i][j] = max(dp[i][j], dp[i][j + 1] + 1)
                    else:
                        dp[i][j] = max(dp[i][j], dp[i][j + 1])
        return max(dp[i][i] for i in range(n))

注：要保证每个状态的结果具有唯一性，例如最短超级串，如果只有mask一维空间则无法返回正确结果，因为相同mask不同拼接顺序的结果可能是不同的，正确代码如下：

class Solution:
    def shortestSuperstring(self, words: List[str]) -> str:
        n = len(words)
        @cache
        def dp(mask, k):
            if mask.bit_count() == n: return (words[k] if k >= 0 else "")
            res = "0" * n * 12
            for i in range(n):
                if (mask >> i) & 1 == 1: continue
                pre = words[k] if k >= 0 else ""
                s = dp(mask | (1 << i), i)
                if pre in s and len(s) < len(res): 
                    res = s
                for j in range(len(pre)):
                    if pre[:len(pre) - j] == s[len(s) - len(pre) + j:]:
                        if len(s + pre[len(pre) - j:]) < len(res):
                            res = s + pre[len(pre) - j:]
                            break
                else:
                    if len(s + pre) < len(res):
                        res = s + pre
            return res
        
        return dp(0, -1)

13、转化转移方程，减少循环 -- 扣分后的最大得分

该题直接使用暴力法超时，代码如下：

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), len(points[0])
        dp = points[0]
        for i in range(1, m):
            temp = [0] * n
            for j in range(n):
                for jj in range(n):
                    temp[j] = max(temp[j], points[i][j] + dp[jj] - abs(j - jj))
            dp = temp
        return max(dp)

最终代码如下：

class Solution:
    def maxPoints(self, points: List[List[int]]) -> int:
        m, n = len(points), len(points[0])
        dp = points[0]
        for i in range(1, m):
            temp = [0] * n
            maxl2 = [-inf]
            for j in reversed(range(n)):
                maxl2.append(max(maxl2[-1], dp[j] - j))

            maxl2 = maxl2[::-1]
            maxl = -inf
            for j in range(n):
                maxl = max(maxl, dp[j] + j)
                temp[j] = max(temp[j], points[i][j] - j + maxl, points[i][j] + j + maxl2[j])
            dp = temp
        return max(dp)

14、使用二分法进行优化 -- 最多可以参加的会议数目 II

class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort(key=lambda e: e[1])
        n = len(events)
        f = [[0] * (k + 1) for _ in range(n + 1)]
        for i, (start, end, val) in enumerate(events):
            p = bisect_left(events, start, hi=i, key=lambda e: e[1])  # hi=i 表示二分上界为 i（默认为 n）
            for j in range(1, k + 1):
                # 为什么是 p 不是 p+1：上面算的是 >= start，-1 后得到 < start，但由于还要 +1，抵消了
                f[i + 1][j] = max(f[i][j], f[p][j - 1] + val)
        return f[n][k]

15、使用单调栈进行优化 -- 工作计划的最低难度

代码如下：

class Solution:
    def minDifficulty(self, a: List[int], d: int) -> int:
        n = len(a)
        if n < d:
            return -1

        f = [[inf] * n for _ in range(d)]
        f[0] = list(accumulate(a, max))
        for i in range(1, d):
            st = []  # (下标 j，从 f[i-1][left[j]] 到 f[i-1][j-1] 的最小值)
            for j in range(i, n):
                mn = f[i - 1][j - 1]  # 只有 a[j] 一项工作
                while st and a[st[-1][0]] <= a[j]:  # 向左一直计算到 left[j]
                    mn = min(mn, st.pop()[1])
                f[i][j] = mn + a[j]  # 从 a[left[j]+1] 到 a[j] 的最大值是 a[j]
                if st:  # 如果这一段包含 <=left[j] 的工作，那么这一段的最大值必然不是 a[j]
                    f[i][j] = min(f[i][j], f[i][st[-1][0]])  # 答案和 f[i][left[j]] 是一样的
                st.append((j, mn))  # 注意这里保存的不是 f[i][j]
        return f[-1][-1]

16、改变递推顺序 -- 通过给定词典构造目标字符串的方案数

如下代码的运行时间为3532ms

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        m, n = len(words[0]), len(target)
        mp = defaultdict(lambda: defaultdict(int))
        for word in words:
            for i, c in enumerate(word):
                mp[c][i] += 1
        mod = 10 ** 9 + 7
        @cache
        def dfs(i, j):
            if i == n: return 1
            res = 0
            for k in range(j, m - (n - i - 1)):      
                if mp[target[i]][k] > 0:
                    res = (res + mp[target[i]][k] % mod * dfs(i + 1, k + 1) % mod) % mod
            return res % mod
        return dfs(0, 0)

改成对于word每个下标是否取用作为递推顺序，代码如下，运行时间为632ms

class Solution:
    def numWays(self, words: List[str], target: str) -> int:
        m, n = len(words[0]), len(target)
        mp = defaultdict(lambda: defaultdict(int))
        for word in words:
            for i, c in enumerate(word):
                mp[c][i] += 1 

        @cache
        def dfs(i, j):
            if i == n: return 1
            if m - j < n - i: return 0
            return (mp[target[i]][j] * dfs(i + 1, j + 1) + dfs(i, j + 1)) % (10 ** 9 + 7)
        return dfs(0, 0)

17、改变状态空间 -- 每个人戴不同帽子的方案数

如果以帽子使用作为状态空间时则超时，代码如下：

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        @cache
        def dfs(mask):
            if mask.bit_count() == len(hats): return 1
            res = 0
            for h in hats[mask.bit_count()]:
                if (mask >> h) & 1 == 0:
                    res = (res + dfs(mask | (1 << h))) % (10 ** 9 + 7)
            return res
        return dfs(0)

如果以人的使用作为状态空间时则通过，这是因为人数不超过10，帽子数为40，帽子的状态空间远远比人的要稀疏，代码如下：

class Solution:
    def numberWays(self, hats: List[List[int]]) -> int:
        mp = defaultdict(list)
        s = set()
        for i, hat in enumerate(hats):
            for a_hat in hat: 
                mp[a_hat].append(i)
                s.add(a_hat)
        s = list(s)
        @cache
        def dfs(i, mask):
            if mask.bit_count() == len(hats): return 1
            if i == len(s): return 0
            res = 0
            for j in mp[s[i]]:
                if (mask >> j) & 1 == 0:
                    res = (res + dfs(i + 1, mask | (1 << j))) % (10 ** 9 + 7)
            res = (res + dfs(i + 1, mask)) % (10 ** 9 + 7)
            return res

        return dfs(0, 0)

18、使用前缀和进行优化 -- 生成数组

class Solution:
    def numOfArrays(self, N: int, M: int, K: int) -> int:
        dp = [[[0 for _ in range(M + 1)] for _ in range(K + 1)] for _ in range(N + 1)]

        for k in range(1, M + 1):
            dp[1][1][k] = 1
        
        for i, j, k in itertools.product(range(1, N + 1), range(1, K + 1), range(M + 1)):
            dp[i][j][k] += dp[i - 1][j][k] * k
            dp[i][j][k] += sum(dp[i - 1][j - 1][1:k])
        
        return sum(dp[N][K][1:]) % (10 ** 9 + 7)

使用前缀和进行优化，以减少重复计算，代码如下：

class Solution:
    def numOfArrays(self, n: int, m: int, k: int) -> int:
        # 不存在搜索代价为 0 的数组
        if k == 0:
            return 0

        f = [[[0] * (m + 1) for _ in range(k + 1)] for __ in range(n + 1)]
        mod = 10**9 + 7
        # 边界条件，所有长度为 1 的数组的搜索代价都为 1
        for j in range(1, m + 1):
            f[1][1][j] = 1
        for i in range(2, n + 1):
            # 搜索代价不会超过数组长度
            for s in range(1, min(k, i) + 1):
                # 前缀和
                presum_j = 0
                for j in range(1, m + 1):
                    f[i][s][j] = (f[i - 1][s][j] * j + presum_j) % mod
                    presum_j += f[i - 1][s - 1][j]
        
        # 最终的答案是所有 f[n][k][..] 的和
        # 即数组长度为 n，搜索代价为 k，最大值任意
        ans = sum(f[n][k][j] for j in range(1, m + 1)) % mod
        return ans

19、改变枚举方式 -- 最小不兼容性

（1）相比于传统回溯方法，使用combinations函数枚举新状态提升枚举速度

（2）对于一个子集没有相同元素的情况，使用哈希表过滤相同元素的方式来减少枚举范围。

（相比于直接枚举，再过滤相同元素有速度提升）

class Solution:
    def minimumIncompatibility(self, nums: List[int], k: int) -> int:
        l = len(nums)
        k = l // k #k转换为每个子集的元素数量
        @lru_cache(None)
        def dfs(state):
            if state == 2 ** l - 1:#已遍历完，返回0
                return 0
            d = {}#哈希表，用于记录每个元素的最后下标
            for i in range(l):
                if state >> i & 1 == 0:#如果未被选，加入哈希表
                    d[nums[i]] = i
            if len(d) < k:#如果非重复数量小于子集元素数量，则无法组合出子集
                return float("inf")
            res = float("inf")
            for it in itertools.combinations(d.keys(), k):#遍历所有组合
                nstate = state#新的状态位
                for j in it:
                    nstate |= 1 << d[j]#根据哈希表更新
                res = min(res, max(it) - min(it) + dfs(nstate))#继续深搜
            return res
        res = dfs(0)
        return res if res < float("inf") else -1

20、使用贪心的方法 -- 连通两组点的最小成本

使用暴力的方法，代码如下，用时3620ms

class Solution:
    def connectTwoGroups(self, cost: List[List[int]]) -> int:
        m, n = len(cost), len(cost[0])
        @cache
        def dfs(i, j, mask, f):
            if i == m: return 0 if mask.bit_count() == n else inf
            if j == n: return dfs(i + 1, 0, mask, 0) if f == 1 else inf
            res = dfs(i, j + 1, mask, f)
            res = min(res, dfs(i, j + 1, mask | (1 << j), 1) + cost[i][j])
            return res
        return dfs(0, 0, 0, 0)

左边只需要和右边的一个点匹配，当匹配完后，右边未匹配的点再贪心匹配左边的点，用时362ms，代码如下：

class Solution:
    def connectTwoGroups(self, s: List[List[int]]) -> int:
        n, m = len(s), len(s[0])
        h = [] # 预处理 h[j] 表示第 j 列的最小值
        for j in range(m):
            h.append(min([s[i][j] for i in range(n)]))
        @cache
        def dfs(p, a):
            # p 表示当前需要匹配的左边组的序号
            if p == n: # 左边的全部都匹配完
                # 将右边组没有匹配的全部与各自能匹配左边组的最小值进行贪心匹配
                return sum([h[j] if ((a >> j & 1) == 0) else 0 for j in range(m)])
            # 与右边的尝试进行一一匹配
            return min([dfs(p + 1, a | (1 << j)) + s[p][j] for j in range(m)])
        return dfs(0, 0)

求解最优路径

1、直接记录路径：（最大整除子集）

dp= [[x] for x in nums]
for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[j] % nums[i] == 0 and len(dp[i]) + 1 > len(dp[j]):
            dp[j] = dp[i] + [nums[j]]
return max(dp, key=len)

2、回溯：（最大整除子集）

maxl, temp = max(dp), None
res, l = [], maxl
for i in reversed(range(n)):
    if l == dp[i]:
        if l == maxl or temp is not None and temp % nums[i] == 0:
            temp = nums[i]
            res.insert(0, nums[i])
            l = l - 1

3、直接返回结果有可能无法保证返回顺序，例如找出分数最低的排列，可以先获取最小值，再递归回溯得到结果集，代码如下：

class Solution:
    def findPermutation(self, nums: List[int]) -> List[int]:
        n = len(nums)
        @cache
        def dp(i, m, last):
            if i == n:
                return 0, []
            minl, res = inf, []
            for j in range(n):
                if (m >> j) & 1 == 1:
                    continue
                if i > 0:
                    tminl, tt = dp(i + 1, m | (1 << j), j) 
                    if tminl + abs(nums[j] - last) < minl:
                        minl = tminl + abs(nums[j] - last)
                        res = [j] + tt
                    elif tminl + abs(nums[j] - last) == minl:
                        if [j] + tt < res:
                            res = [j] + tt

                else:
                    tminl, tt = dp(i + 1, m | (1 << j), j)
                    if tminl + abs(nums[j] - tt[-1]) < minl:
                        minl = tminl + abs(nums[j] - tt[-1])
                        res = [j] + tt
                    elif tminl + abs(nums[j] - tt[-1]) == minl:
                        if [j] + tt < res:
                            res = [j] + tt
  
            return minl, res
        
        minl = dp(0, 0, -1)[0]
        
        res = []
        def dfs(m, s, r, last, zero):
            nonlocal res
            if res != []: return 
            if m.bit_count() == n:
                if s + abs(nums[zero] - last) == minl:
                    res = r
                return 

            if s > minl: return 
            for j in range(n):
                if (m >> j) & 1 == 1:
                    continue
                if m.bit_count() > 0:
                    dfs(m | (1 << j), s + abs(nums[j] - last), r + [j], j, zero) 
                else:
                    dfs(m | (1 << j), s, r + [j], j, j)
        
        dfs(0, 0, [], -1, -1)
        return res

注：使用记忆化搜索有可能会导致超时，例如1770. 执行乘法运算的最大分数，所以可以使用del func 或者func.cache_clear()清除缓存