力扣刷题记录&整理——（十四）2-D Dynamic Programming

---

前言

整理力扣刷题思路。

• 语言：python
• 题库：来自neetcode: link

---

一、预备知识

---

二、解题思路

1.动态规划

62.unique-paths

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？
link

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        dp = [[1]*n for _ in range(m)]
        dp[0][0:] = [1] * n
        dp[0:][0] = [1] * m
        
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]
1
2
3
4
5
6
7
8
9
10
11
12

1143.longest-common-subsequenc

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

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

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

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]
1
2
3
4
5
6
7
8
9
10
11
12

309.best-time-to-buy-and-sell-stock-with-cooldown

给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
link

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        if n==1:
            return 0
        
        #dp[i][0]代表第i天正持有股票的最大收益，dp[i][1]则是未持有股票
        dp = [[0]*2 for _ in range(n)]
        dp[0][1] = -prices[0]
        for i in range(1,n):
            dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
            dp[i][1] = max(dp[i-1][1], dp[i-2][0]-prices[i])
        return dp[-1][0]
1
2
3
4
5
6
7
8
9
10
11
12
13

参考：link

97.interleaving-string

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的。

两个字符串 s 和 t 交错 的定义与过程如下，其中每个字符串都会被分割成若干 非空
子字符串
：

s = s1 + s2 + … + sn
t = t1 + t2 + … + tm
|n - m| <= 1
交错 是 s1 + t1 + s2 + t2 + s3 + t3 + … 或者 t1 + s1 + t2 + s2 + t3 + s3 + …
注意：a + b 意味着字符串 a 和 b 连接。
link

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1)+len(s2) != len(s3):
            return False
        if not s1:
            return s2==s3
        if not s2:
            return s1==s3
        
        #dp[i][j]代表s1的前i个字符与s2的前j个字符是否能组成s3的前i+j个字符
        dp = [[False]*(len(s2)+1) for _ in range((len(s1)+1))]
        dp[0][0] = True
        for i in range(1,len(s1)+1):
            if dp[i-1][0]:
                dp[i][0] = (s1[i-1]==s3[i-1])
        for j in range(1,len(s2)+1):
            if dp[0][j-1]:
                dp[0][j] = (s2[j-1]==s3[j-1])
        for i in range(1,len(s1)+1):
            for j in range(1,len(s2)+1):
                dp[i][j] = (dp[i-1][j] and s1[i-1]==s3[i+j-1]) or (dp[i][j-1] and s2[j-1]==s3[i+j-1])
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

根据题目要求优化空间：

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1)+len(s2) != len(s3):
            return False
        if not s1:
            return s2==s3
        if not s2:
            return s1==s3
        
        dp = [False]*(len(s2)+1)
        dp[0] = True

        for j in range(1,len(s2)+1):
            if dp[j-1]:
                dp[j] = (s2[j-1]==s3[j-1])

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

        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

72.edit-distance

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

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

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

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if not word1:
            return len(word2)
        if not word2:
            return len(word1)
        
        #dp[i][j]代表word1的前i个字符转换成word2的前j个字符所需的最少操作数
        dp = [[0]*(len(word2)+1) for _ in range((len(word1)+1))]
        for i in range(1, len(word1) + 1):
            dp[i][0] = i
        for j in range(1, len(word2) + 1):
            dp[0][j] = j
        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],dp[i][j-1],dp[i-1][j-1]) + 1

        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

改进空间：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        if not word1:
            return len(word2)
        if not word2:
            return len(word1)
        
        dp = list(range(len(word2)+1))
        for i in range(1,len(word1)+1):
            pre = dp[0]
            dp[0] = i
            for j in range(1,len(word2)+1):
                if word1[i-1]==word2[j-1]:
                    dp[j],pre = pre, dp[j]
                else:
                    dp[j],pre = min(dp[j],dp[j-1],pre) + 1, dp[j]

        return dp[-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

312.burst-balloons

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。

现在要求你戳破所有的气球。戳破第 i 个气球，你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。

求所能获得硬币的最大数量。
link

class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums = [1] + nums + [1]
        dp = {}
        def dfs(l,r):
            if l>r:
                return 0
            if (l,r) in dp:
                return dp[(l,r)]
            
            #dp[(l,r)]代表从第l个到第r个气球最多能获得多少个金币
            dp[(l,r)] = 0
            #遍历的i代表最后一个戳破的气球
            for i in range(l,r+1):
                coin = dfs(l,i-1) + nums[l-1]*nums[i]*nums[r+1] + dfs(i+1,r)
                dp[(l,r)] = max(dp[(l,r)], coin)

            return dp[(l,r)]
        
        return dfs(1,len(nums)-2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

参考neetcode视频

115.distinct-subsequences

给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
link

class Solution:
    def numDistinct(self, s: str, t: str) -> int:
        m,n = len(t),len(s)
        if m>n:
            return 0
        
        #dp[i][j]代表t的前i个字符在s的前j个字符的子序列中出现的个数
        dp = [[0]*(n+1) for _ in range(m+1)]
        dp[0] = [1]*(n+1)
        for i in range(1,m+1):
            for j in range(1,n+1):
                if t[i-1] != s[j-1]:
                    dp[i][j] = dp[i][j-1]
                else:
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1]
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

参考：link

10.regular-expression-matching

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。
link

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m,n = len(s),len(p)

        #dp[i][j]表示s的前i个字符和p的前j个字符能否匹配
        dp = [[False]*(n+1) for _ in range(m+1)]
        dp[0][0] = True
        for j in range(1,n+1):
            if p[j-1]=='*':
                dp[0][j] = dp[0][j-2]
        
        for i in range(1,m+1):
            for j in range(1,n+1):
                if s[i-1]==p[j-1] or p[j-1]=='.':
                    dp[i][j] = dp[i-1][j-1]
                elif p[j-1]=='*':
                    if s[i-1]!=p[j-2] and p[j-2]!='.':
                        dp[i][j] = dp[i][j-2]
                    else:
                        dp[i][j] = dp[i][j-2]|dp[i-1][j]
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

参考：link

2.背包问题

518.coin-change-ii

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

题目数据保证结果符合 32 位带符号整数。
link

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        n = len(coins)
        dp = [[0]*(amount+1) for _ in range(n+1)]
        dp[0][0] = 1
        for i in range(1,n+1):
            for j in range(amount+1):
                if coins[i-1]>j:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-coins[i-1]]
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12

494.target-sum

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：

例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
link

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if total < abs(target) or (total+target)%2 == 1:
            return 0
        
        pos = (total+target)//2
        neg = (total-target)//2
        capacity = min(pos,neg)
        dp = [[0]*(capacity+1) for _ in range(len(nums)+1)]
        dp[0][0] = 1
        for i in range(1,len(nums)+1):
            for j in range(capacity+1):
                if j<nums[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]]
        return dp[-1][-1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

参考：link
解法很巧妙，将问题转化成0-1背包问题