动态规划经典问题整理

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

双序列

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)

背包问题

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)

状态压缩与优化

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、使用位运算存储状态：（1012. 至少有 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)

5、使用26个字母空间（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)

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])

动态规划与树结合

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

求解最优路径

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

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

参考资料

史上最全最丰富的“最长公共子序列”、“最长公共子串”问题的解法与思路_王小东大将军的博客-CSDN博客_最长公共子序列问题

动态规划-----两个字符串交叉组成第三个字符

动态规划解决01背包问题 - Christal_R - 博客园

最大连续子序列之和练习最大m子段和_QiaoRuoZhuo的专栏-CSDN博客

动态规划总结及题目推荐_IMLYZ的博客-CSDN博客

动态规划之背包问题系列 - 知乎

原文链接：https://blog.csdn.net/u014595589/article/details/82716230