动态规划

1. 动态规划简介

动态规划（Dynamic programming，简称 DP），是一种把 原问题分解为相对简单的子问题 的解题方法。

• 动态规划不是某一具体的算法，而是一种算法思想。
• 与 分治 相比较，核心思想都是减小问题的规模，但分治不存在重复子问题，这是二者的区别。
• 与 贪心 相比较，贪心只用解决其中 一个子问题 就行了。

2. 线性动态规划

这类问题的要点：

• 状态定义，如 dp[n] 表示问题规模为 n 的解
• 状态转移方程
• 初始化和边界条件

2.1 单串问题

2.1.1 单串LIS系列

LIS 是 longest-increasing-subsequence 的缩写

300. 最长递增子序列

给定一个无序的整数数组，找到其中最长上升子序列的长度。

输入: [10,9,2,5,3,7,101,18]
输出: 4
解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。

# 方法一：DP---O(n^2)
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0
        dp = []
        for i in range(len(nums)):
            dp.append(1)
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j]+1)
        return max(dp)

# 方法二：贪心+二分查找---O(nlogn)
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        d=[]
        for num in nums:
            if not d or num>d[-1]: d.append(num)
            else:
                l,r=0,len(d)-1
                loc=r
                while l<=r:
                    mid=(l+r)//2
                    if d[mid]>=num:
                        loc=mid
                        r=mid-1
                    else: l=mid+1
                d[loc]=num
        return len(d)

#在nums的遍历中
#1.如果num比末尾大，则直接加入到数组d末尾。
#2.否则，在数组d中二分查找，找到第一个比num小的数d[k]，并更新 d[k + 1]=min(d[k+1],num)=num。

673. 最长递增子序列的个数

class Solution(object):
    def findNumberOfLIS(self, nums):
        n = len(nums)
        dp = [0]*n
        cnt = [1]*n
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[i] == dp[j] + 1:
                        cnt[i] += cnt[j]
                    elif dp[i] < dp[j] + 1:
                        dp[i] = dp[j] + 1
                        cnt[i] = cnt[j]
        length = max(dp)
        return sum(cnt[i] for i,l in enumerate(dp) if l==length)

2.1.2 最大子数组和系列

53. 最大子序和

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1, len(nums)):
            nums[i] += max(0, nums[i-1])
        return max(nums)

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

维持 minn 和 maxn

class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        res = float('-inf')
        minn, maxn = 1, 1
        for num in nums:
            a = minn*num
            b = maxn*num
            minn = min(num, a, b)
            maxn = max(num, a, b)
            res = max(res,maxn)
        return res

918. 环形子数组的最大和⭐

无环情况下，dp1 为最大子序和
有环情况下， sum(nums) - min(dp2) 为额外的结果

class Solution:
    def maxSubarraySumCircular(self, nums: List[int]) -> int:
        if all([num<0 for num in nums]): return max(nums)
        n = len(nums)
        dp1 = [0]*n
        dp2 = [0]*n
        dp1[0] = nums[0]
        dp2[0] = nums[0]

        for i in range(1,n):
            dp1[i] = max(nums[i], nums[i]+dp1[i-1])     #最大子序和
            dp2[i] = min(nums[i],nums[i]+dp2[i-1])      #最小子序和

        return max(dp1+[sum(nums)-min(dp2)])

面试题 17.24. 最大子矩阵⭐

枚举上下边界，再进行一个最大子序和。前缀和优化一下，时间击败100%

class Solution:
    def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
        rows, cols = len(matrix), len(matrix[0])
        d = [list(accumulate(x)) for x in zip(*matrix)]
        d = [[0]*cols] + [i for i in zip(*d)]

        res = []
        val = float('-inf')

        for r1 in range(rows):
            for r2 in range(r1, rows):
                arr = [x - y for x,y in zip(d[r2+1],d[r1])]
                cur = 0
                for c2 in range(cols):
                    if cur <= 0:
                        c1 = c2
                        cur = arr[c2]
                    else:
                        cur += arr[c2]

                    if cur > val:
                        val = cur
                        res = [r1, c1, r2, c2]
        
        return res

2.1.3 打家劫舍系列

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

常规做法：

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n<3: return max(nums)
        dp = [0]*n
        dp[0] = nums[0]
        dp[1] = max(nums[:2])

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

状态化简做法：

class Solution:
    def rob(self, nums: List[int]) -> int:
        a, b = nums[0], max(nums[:2])
        for i in range(2, len(nums)):
            a, b = b, max(b, nums[i] + a)
        return b

213. 打家劫舍 II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

分成两个打家劫舍来做

class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums: return 0
        n = len(nums)
        if n < 3: return max(nums)
        dp1, dp2 = [0]*n, [0]*n
        dp1[1] = nums[0]
        dp2[1] = nums[1]
        for i in range(2,n):
            dp1[i] = max(dp1[i-1],dp1[i-2]+nums[i-1])
        for i in range(3,n+1):
            dp2[i-1] = max(dp2[i-2],dp2[i-3]+nums[i-1])
        return max(dp1+dp2) 

740. 删除并获得点数

可以转换为打家劫舍问题

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        arr = [0]*(max(nums)+1)
        for num in nums:
            arr[num] += num
        a, b = arr[0], max(arr[:2])

        for i in range(2, len(arr)):
            a, b = b, max(b, a+arr[i])
        return b

2.1.4 股票系列

121. 买卖股票的最佳时机

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cost = float('inf')
        res = 0
        for p in prices:
            cost = min(p,cost)
            res = max(res, p-cost)
        return res

122. 买卖股票的最佳时机 II

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        for i in range(1, len(prices)):
            res += max(0, prices[i]-prices[i-1])
        return res

123. 买卖股票的最佳时机 III

188. 买卖股票的最佳时机 IV

2.2 双串问题

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

输入：text1 = "abcde", text2 = "ace"
输出：3
解释：最长公共子序列是 "ace"，它的长度为 3。

#方法一：DP
# dp[i][j] 表示 text1[:i]，text2[:j] 的最长公共子序列

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            for j in range(1, n+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])
        
        return dp[m][n]

#方法二：
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if text1 == text2:
            return len(text1)
        #if not set(text1).intersection(text2):
           # return 0
        
        d = collections.defaultdict(list)
        m, n = len(text1), len(text2)
        for i in range(n-1, -1, -1):
            d[text2[i]].append(i)
            
        nums = []
        for c in text1:
            if c in d:
                nums.extend(d[c])
        
        ans = []
        for num in nums:
            idx = bisect.bisect_left(ans, num)
            if idx == len(ans):
                ans.append(num)
            else:
                ans[idx] = num
        return len(ans)

516. 最长回文子序列⭐

给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0]*n for _ in range(n)]

        for i in range(n-1, -1, -1):
            dp[i][i] = 1
            for j in range(i+1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                else:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        
        return dp[0][n-1]

5. 最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n<2: return s

        max_len = 1
        begin = 0
        dp = [[0]*n for _ in range(n)]  #用于记录是否回文
        for i in range(n):
            dp[i][i] = 1
        
        for l in range(2, n+1):    #开始枚举长度
            for i in range(n):
                j = i + l - 1
                if j >= n: 
                    break
                if s[i] != s[j]:
                    dp[i][j] = 0
                else:
                    if l < 4:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = dp[i+1][j-1]

                if dp[i][j] and l > max_len:
                    max_len = l
                    begin = i
        
        return s[begin:begin+max_len]

# 时间复杂度：O(n^2)
# 空间复杂度：O(n^2)

还有一个复杂度为 O(n) 的 Manacher 算法。

583. 两个字符串的删除操作

给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

# 方法一：DP

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            dp[i][0] = i
        for j in range(1, n+1):
            dp[0][j] = j

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

# 方法二：仿LCS（最长公共子序列）

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        dp = [[0]*(n+1) for _ in range(m+1)]


        for i in range(1, m+1):
            for j in range(1, n+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        
        lcs = dp[m][n]
        return m-lcs+n-lcs

72. 编辑距离⭐

dp[i][j] 表示 word1 的前 i 个字母和 word2 的前 j 个字母之间的编辑距离

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        dp = [[0]*(n+1) for _ in range(m+1)]

        for i in range(1, m+1):
            dp[i][0] = i
        for j in range(1, n+1):
            dp[0][j] = j

        for i in range(1, m+1):
            for j in range(1, n+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],dp[i][j-1],dp[i-1][j-1]) + 1
        
        return dp[-1][-1]

太抽象了，dp 这也能做出来

2.3 矩阵问题

3. 前缀和

4. 区间动态规划

5. 背包动态规划

322. 零钱兑换

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

279. 完全平方数

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n，返回和为 n 的完全平方数的 最少数量 。

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] + [float('inf')]*n

        for i in range(1, n+1):
            j = 1
            while j*j <= i:
                dp[i] = min(dp[i], dp[i-j*j]+1)
                j += 1
        
        return dp[n]

6. 状态压缩动态规划

状态压缩

用一个变量来表示当前状态。

比较常用的方式是利用一个 n 位 k 进制数 mask 表示当前 n 个节点的所处的 k 个不同状态。

比如 "0101" 可表示第0个物品未携带，第1个物品已携带，依此类推。

7. 计数问题

62. 不同路径

1. 动态规划

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0]*n for _ in range(m)]

        for i in range(m):
            for j in range(n):
                if not i: dp[i][j] = 1
                elif not j: dp[i][j] = 1
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[-1][-1]

2. 使用公式

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        return comb(m+n-2,m-1)

8. 矩阵快速幂

50. Pow(x, n)

分治，将大问题化简为小问题

class Solution:
    def myPow(self, x: float, n: int) -> float:
        def fun(n):
            if n == 0:
                return 1.0
            y = fun(n//2)
            return y*y if n%2==0 else x*y*y

        return fun(n) if n>=0 else 1.0/fun(-n)

70. 爬楼梯

矩阵快速幂做法，能将 DP 的 O(n) 降低至 O(logn)

这题还有通项公式做法…

9. 数位动态规划

10. 暂未归类

337. 打家劫舍 III

在上次打劫完一条街道之后和一圈房屋后，小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为“根”。 除了“根”之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果两个直接相连(即父与子关系）的房子在同一天晚上被打劫，房屋将自动报警。

计算在不触动警报的情况下，小偷一晚能够盗取的最高金额。

class Solution:
    def rob(self, root: TreeNode) -> int:
        return self.helper(root)[1]

    def helper(self, root):
        if not root: return [0,0]
        lv=self.helper(root.left)
        rv=self.helper(root.right)
        return [lv[1] + rv[1], max(lv[1] + rv[1], root.val + lv[0] + rv[0])]

#树形DP，从树的左下构成一个表。
#helper函数返回列表[不含此节点最大值，含此节点最大值]
#经典

LCP 19. 秋叶收藏集

小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 leaves， 字符串 leaves 仅包含小写字符 r 和 y， 其中字符 r 表示一片红叶，字符 y 表示一片黄叶。

出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

#方法一：dp
#    dp[i][0]表示全部为红需要修改几次
#    dp[i][1]表示【红黄】需要修改几次
#    dp[i][2]表示【红黄红】需要修改几次

class Solution:
    def minimumOperations(self, leaves: str) -> int:
        n=len(leaves)
        dp=[[0  for i in range(3)] for i in range(n)]
        dp[0][0]= 0 if leaves[0]=='r' else 1
        #print(dp)
        for i in range(1,n):
            dp[i][0]=dp[i-1][0]+(0 if leaves[i]=='r' else 1)
            dp[i][1]=dp[i-1][0]+(0 if leaves[i]=='y' else 1)
            if i>1:
                dp[i][1]=min(dp[i][1],dp[i-1][1]+(0 if leaves[i]=='y' else 1))
                dp[i][2]=dp[i-1][1]+(0 if leaves[i]=='r' else 1)
            if i>2:
                dp[i][2]=min(dp[i][2],dp[i-1][2]+(0 if leaves[i]=='r' else 1))
        #for i in dp: print(i)
        return dp[n-1][2]

# dp表时用[0]*3建表会出错

664. 奇怪的打印机

有台奇怪的打印机有以下两个特殊要求：

• 打印机每次只能打印由 同一个字符 组成的序列。
• 每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。

class Solution:
    def strangePrinter(self, s: str) -> int:
        n = len(s)
        dp = [[n]*n for _ in range(n)]
        for i in range(n-1,-1,-1):
            dp[i][i] = 1
            for j in range(i+1,n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i][j-1]
                else:
                    dp[i][j] = min([dp[i][k]+dp[k+1][j] for k in range(i,j)])
        return dp[0][n-1]

# dp 666

375. 猜数字大小 II

dp核心思想：规模较大的问题可以转换为类似的小规模问题

class Solution:
    def getMoneyAmount(self, n: int) -> int:
        dp = [[0]*(n+1) for _ in range(n+1)]

        for i in range(n-1, 0, -1):
            for j in range(i+1, n+1):
                dp[i][j] = min([x + max([dp[i][x-1],dp[x+1][j]]) for x in range(i,j)])

        return dp[1][n]

91. 解码方法

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        f = [1] + [0]*n

        for i in range(1, n+1):
            if s[i-1] != "0":
                f[i] += f[i-1]
            if i>1 and s[i-2]!='0' and int(s[i-2:i])<=26:
                f[i] += f[i-2]
        
        return f[n]

639. 解码方法 II

class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [1] + [0]*n

        if s[0] == '*':
            dp[1] = 9
        elif s[0] == '0':
            return 0
        else:
            dp[1] = 1

        for i in range(1, n):
            if s[i] == '0':
                if s[i-1] == '1' or s[i-1] == '2':
                    dp[i+1] = dp[i-1]
                elif s[i-1] == '*':
                    dp[i+1] = dp[i-1] * 2
                else:
                    return 0
            elif s[i] == '*':
                if s[i-1] == '1':
                    dp[i+1] = dp[i]*9 + dp[i-1]*9
                elif s[i-1] == '2':
                    dp[i+1] = dp[i]*9 + dp[i-1]*6
                elif s[i-1] == '*':
                    dp[i+1] = dp[i]*9 + dp[i-1]*6 + dp[i-1]*9
                else:
                    dp[i+1] = dp[i]*9
            elif s[i] in ['1','2','3','4','5','6']:
                if s[i-1] == '*':
                    dp[i+1] = dp[i] + dp[i-1]*2
                elif s[i-1] in ['1', '2']:
                    dp[i+1] = dp[i] + dp[i-1]
                else:
                    dp[i+1] = dp[i]
            else:
                if s[i-1] in ['*', '1']:
                    dp[i+1] = dp[i] + dp[i-1]
                else:
                    dp[i+1] = dp[i]
            dp[i+1] %= (10**9 + 7)
        return dp[-1]