2022-02-19 动态规划高频题专题【1】

动态规划基本类型

• dp基础
• 背包问题
• 打家劫舍
• 股票问题
• 子序列问题
• 进阶动态规划

深入理解动态规划过程

• 定义dp数组需要理解dp是什么，下标是什么：基本dp一般都是一维dp[i]，子序列问题经常是二维的dp[i][j]，对于dp是什么通常是问题需要求解的参数，一般是一个数值。
• 寻求递推公式：很关键，但是只是一部分
• dp数组的初始化：怎么初始化取决于如何理解dp数组的含义，每类题型实际上初始化都有些差异
• 状态执行中的遍历顺序（内外层循环置换？顺序遍历还是逆序遍历）：背包问题对于这一点就很讲究
• 打印dp数组：通过dp数组可以看出问题出在哪里，通常用来调试

72. 编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

示例 2：

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

提示：

0 <= word1.length, word2.length <= 500
word1 和 word2 由小写英文字母组成

分析：

• 状态构造：dp[i][j]表示word1的前i个字母转换成word2的前j个字母所使用的最少操作。
• 状态转移：i指向word1，j指向word2
  • 若当前字母相同，则dp[i][j] = dp[i - 1][j - 1];
  • 否则取增删替三个操作的最小值 + 1， 即: dp[i][j] = min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) + 1。

题解：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        n1 = len(word1)
        n2 = len(word2)
        dp = [[0] * (n2 + 1) for _ in range(n1 + 1)]
        # 第一行
        for j in range(1, n2 + 1):
            dp[0][j] = dp[0][j-1] + 1
        # 第一列
        for i in range(1, n1 + 1):
            dp[i][0] = dp[i-1][0] + 1
        for i in range(1, n1 + 1):
            for j in range(1, n2 + 1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
                else:
                    dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1] ) + 1
        #print(dp)      
        return dp[-1][-1]

总结：对于两个序列进行动态规划，通常要升到二维数组取考虑状态，不能局限与1维

300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

1 <= nums.length <= 2500
-104 <= nums[i] <= 104

分析：

• dp[i]的定义：dp[i]表示i之前包括i的最长上升子序列的长度
• 状态转移方程：位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
• 初始值：每一个i，对应的dp[i]（即最长上升子序列）起始大小至少都是是1.
• 确定遍历顺序：dp[i] 是有0到i-1各个位置的最长升序子序列 推导而来，那么遍历i一定是从前向后遍历。j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层

题解：

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        l = len(nums)
        dp = [1] * l

        ans = 1

        for i in range(l):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

            if dp[i] > ans:
                ans = dp[i]

        return ans

总结：对于上述采用动态规划方法，时间复杂度明显是O(n^2)
进阶：能将算法的时间复杂度降低到 O(n log(n)) 吗?
思路：需要利用二分查找的方法解决。

5. 最长回文子串

• 暴力解法：两层for循环，遍历区间起始位置和终止位置，然后判断这个区间是不是回文。时间复杂度：O(n^3)

动态规划分析：

• 确定dp数组（dp table）以及下标的含义：布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。

• 确定递推公式：在确定递推公式时，就要分析如下几种情况。整体上是两种，就是s[i]与s[j]相等，s[i]与s[j]不相等这两种。

  • 当s[i]与s[j]不相等，那没啥好说的了，dp[i][j]一定是false。
  • 当s[i]与s[j]相等时，这就复杂一些了，有如下三种情况
    • 情况一：下标i 与 j相同，同一个字符例如a，当然是回文子串
    • 情况二：下标i 与 j相差为1，例如aa，也是文子串
    • 情况三：下标：i 与 j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，我们看i到j区间是不是回文子串就看aba是不是回文就可以了，那么aba的区间就是 i+1 与 j-1区间，这个区间是不是回文就看dp[i + 1][j - 1]是否为true。

• dp数组如何初始化：dp[i][j]可以初始化为true么？ 当然不行，怎能刚开始就全都匹配上了。所以dp[i][j]初始化为false。

• 确定遍历顺序：首先从递推公式中可以看出，情况三是根据dp[i + 1][j - 1]是否为true，在对dp[i][j]进行赋值true的。dp[i + 1][j - 1] 在 dp[i][j]的左下角，如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。有的代码实现是优先遍历列，然后遍历行，其实也是一个道理，都是为了保证dp[i + 1][j - 1]都是经过计算的。

题解：

class Solution:
    def longestPalindrome(self, s: str) -> str:
        l = len(s)
        dp = [[False] * l for _ in range(l)]

        maxlen = 0
        left = 0
        right = 0

        for i in range(l-1, -1, -1):
            for j in range(i, l):
                if s[i] == s[j] and (j - i <= 1 or dp[i+1][j-1]):
                        dp[i][j] = True

                if dp[i][j] and j - i + 1 > maxlen:
                    maxlen = j - i + 1
                    left = i
                    right = j 

        return s[left:right+1]

总结：注意这里的dp代表的布尔值，子序列问题如果一维不好解决就需要用二维来存储，当然动态规划方案的时间复杂度和空间复杂度都是O(n^2)，优化空间可以使用双指针的方式。

1143. 最长公共子序列

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

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，"ace" 是 "abcde" 的子序列，但 "aec" 不是 "abcde" 的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。

示例 1：

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

示例 2：

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

示例 3：

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

提示：

1 <= text1.length, text2.length <= 1000
text1 和 text2 仅由小写英文字符组成。

分析：

• 确定dp数组（dp table）以及下标的含义：dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列长度为dp[i][j]

• 确定递推公式：主要就是两大情况： text1[i - 1] 与 text2[j - 1]相同，text1[i - 1] 与 text2[j - 1]不相同

  • 如果text1[i - 1] 与 text2[j - 1]相同，那么找到了一个公共元素，所以dp[i][j] = dp[i - 1][j - 1] + 1;
  • 如果text1[i - 1] 与 text2[j - 1]不相同，那就看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。
  • 即：dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

• dp数组如何初始化：test1[0, i-1]和空串的最长公共子序列自然是0，所以dp[i][0] = 0;
  同理dp[0][j]也是0。其他下标都是随着递推公式逐步覆盖，初始为多少都可以，那么就统一初始为0。

题解：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        m = len(text1) + 1
        n = len(text2) + 1

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

        maxlen = 0 

        for i in range(1, m):
            for j in range(1, n):
                if text1[i-1] in text2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])

                if dp[i][j] > maxlen:
                    maxlen = dp[i][j]

        return maxlen

总结：注意对比此题与编辑距离一题的相似之处

42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

n == height.length
1 <= n <= 2 * 104
0 <= height[i] <= 105

分析：

• 前缀最值与后缀最值的结合，对于一个位置，该位置可以装水的数目为前缀最大与后缀最大中较小的减去当前高度，即min(prev_min[i], prev_max[i]) - height[i]

题解：

class Solution:
    def trap(self, height: List[int]) -> int:
        l = len(height)
        prev_min = [0] * l
        prev_max = [0] * l

        prev_min[0] = height[0]
        prev_max[-1] = height[-1]

        for i in range(1, l):
            prev_min[i] = max(prev_min[i-1], height[i])

        for j in range(l-2, -1, -1):
            prev_max[j] = max(prev_max[j+1], height[j])

        sum = 0    

        for i in range(l):
            sum += min(prev_min[i], prev_max[i]) - height[i]

        return sum

更多解法：参考

152. 乘积最大子数组

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

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

提示:

1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10
nums 的任何前缀或后缀的乘积都 保证 是一个 32-位 整数

分析：

• 与连续子序列和问题相似，该题是连续子序列积问题。思路与“和”差不多，但是成绩存在正负号的问题，导致当前dp最大值不仅取决于上个dp的最大值，还取决于其上一个dp的最小值
• 补充：对于乘积与加和的连续可以通过对数域和指数域进行转换。

题解：

class Solution:

    def maxProduct(self, nums: List[int]) -> int:
        
        l = len(nums)
        dp_max = [0] * l
        dp_min = [0] * l
        dp_max[0] = nums[0]
        dp_min[0] = nums[0]

        ans = nums[0]

        for i in range(1, l):
            dp_max[i] = max(nums[i], dp_max[i-1] * nums[i], dp_min[i-1] * nums[i])
            dp_min[i] = min(nums[i], dp_min[i-1] * nums[i], dp_max[i-1] * nums[i])
            ans = max(ans, dp_max[i])
        return ans

64. 最小路径和

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

分析：

• 状态含义：dp数组为二维，dp[i][j]表示从开始位置到第i行与第j列的路径最小值。
• 状态转移：dp[i][j]可由dp[i-1][j] + grid[i][j] 与dp[i][j-1] + grid[i][j]的最小值
• 状态初始化：需要对dp的第一列和第一行初始化，初始化是从开始位置横向或竖向到达该位置的最小值
• 遍历顺序：从左上角向右下角遍历

题解：

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

        dp[0][0] = grid[0][0]

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

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

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

        return dp[-1][-1]

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

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

示例 3：

输入：prices = [7,6,4,3,1] 
输出：0 
解释：在这个情况下, 没有交易完成, 所以最大利润为 0。

示例 4：

输入：prices = [1]
输出：0

提示：

1 <= prices.length <= 10^5
0 <= prices[i] <= 10^5

分析：

• 拆分两个dp问题，第1天到第i天的收益最大值与第i天到最后一天的收益最大值
• 根据需要的变量构建三维的dp数组进行动态规划：第一维表示天，第二维表示交易了几次，第三维表示是否持有股票

题解：
方法一：将问题转化为第i天前买卖和第i天后买卖收益之和最大的结果

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        l = len(prices)
        if l < 2:
            return 0

        dp1 = [0] * l
        dp2 = [0] * l
        dp = [0] * l

        min_val = prices[0]
        max_val = prices[-1]

        for i in range(1, l):
            dp1[i] = max(dp1[i-1], prices[i] - min_val)
            min_val = min(prices[i], min_val)

        for j in range(l-2, -1, -1):
            dp2[j] = max(dp2[j+1], max_val - prices[j])
            max_val = max(max_val, prices[j])

        for i in range(l):
            dp[i] = dp1[i] + dp2[i]

        return max(dp)
   

方法二：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0
        n = len(prices)
        dp = [[[0]*2 for _ in range(3)] for _ in range(n)]
        # dp[i][j][0]表示第i天交易了j次时不持有股票, dp[i][j][1]表示第i天交易了j次时持有股票
        # 定义卖出股票时交易次数加1
        for i in range(3):
            dp[0][i][0], dp[0][i][1] = 0, -prices[0]
        
        for i in range(1, n):
            for j in range(3):
                if not j:
                    dp[i][j][0] = dp[i-1][j][0]
                else:
                    dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j-1][1] + prices[i])
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0] - prices[i])
        
        return max(dp[n-1][0][0], dp[n-1][1][0], dp[n-1][2][0])

总结：从分析的变量属性与取值考虑dp数组新的维度。