1. Toy模板网首页
  2. > Toy博客

Leetcode题解-算法-动态规划（python版）

10月前 作者：-出发- 分类：Toy博客 阅读(50) 违法举报

这篇具有很好参考价值的文章主要介绍了Leetcode题解-算法-动态规划（python版）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、斐波那契数列

1.1 爬楼梯

70. 爬楼梯(Easy)
走n阶楼梯的方法有两种，1、先走 1 级台阶，再走 n-1 级台阶；2、先走 2 级台阶，再走 n-2 级台阶
f(n) = f(n-1) + f(n-2)

class Solution:
    def climbStairs(self, n: int) -> int:
        pre, cur= 1, 1
        for i in range(1, n):
            tmp = cur
            cur = pre + cur
            pre = tmp
        return cur

1.2 强盗抢劫

198. 打家劫舍(Medium)
每个房间财产为 nums[0]……nums[n-1]。

假设 0 至 x 间房获得的最大财产为 f(x)。
f(x) = max(f(x-1),f(x-2)+nums[x])
如果不拿房间 x 的财产，可以获得的总财产为 f(x-1)，如果拿房间 x 的财产，可以获得的总财产为 f(x-2)+nums[x]，二者取最大值就是 0-x 房间可以获得的最大财产。

class Solution:
    def rob(self, nums: List[int]) -> int:
        pre, cur = 0, 0
        for num in nums:
            tmp = cur
            cur = max(cur, pre + num)
            pre = tmp
        return cur

1.3 环形街道抢劫

213. 打家劫舍 II(Medium)

转换为非环形街道求解，求从第一个到倒数第二个房子的最大财宝数。再求第二个到倒数第一个房子的最大财宝数。取二者最大值。

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 0: return 0
        if n== 1: return nums[0]

        def rob_line(nums, left, right):
            pre, cur = 0, 0
            for i in range(left, right+1):
                tmp = cur
                cur = max(cur, pre + nums[i])
                pre = tmp
            return cur
        
        return max(rob_line(nums, 1, n-1), rob_line(nums, 0, n-2))

2、矩阵路径

2.1 矩阵的最小的路径和

64. 最小路径和(Medium)

找出矩阵的左上角到右下角的最小路径和，每次只能向右和向下移动。

问题分析：
子问题：第 i 行第 j 列的元素到右下角的路径和。
递推公式：
grid[i][j] = min( grid[i][j+1], grid[i+1][j] ) + grid[i][j];

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        row = len(grid)
        col = len(grid[0])

        for i in range(1, col):
            grid[0][i] += grid[0][i-1]
        for i in range(1, row):
            grid[i][0] += grid[i-1][0]
        
        for i in range(1, row):
            for j in range(1, col):
                grid[i][j] += min(grid[i][j-1], grid[i-1][j])
        return grid[-1][-1]

2.2 矩阵的总路径数

62. 不同路径(Medium)
方法一：动态规划

子问题：从 i 行 j 列走到矩阵左上角多少种走法；
边界条件：在第一行或者第一列，只有一种走法；
递推公式：vec[i][j] = vec[i][j-1] + vec[i-1][j]; 表示从某一点到左上角的走法等于，先向左走一步的走法和先向上走一步走法之和。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1
        vec = [[1] * n for i in range(m)]

        for i in range(1, m):
            for j in range(1, n):
                vec[i][j] = vec[i - 1][j] + vec[i][j - 1]
        return vec[-1][-1]

方法二：组合数学
这道题可以用公式求解，是组合问题。机器人总共移动的次数 S=m+n-2，向下移动的次数 D=m-1，从 S 个位置中取出 D 个，有多少种方法，这个问题的解为 C(S, D)。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        S = m+n-2
        D = m-1
        res = 1
        for i in range(1, D+1):
            res = res * (S-D+i)/i
        return int(res)

或者

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

3、数组区间

3.1 数组区间和

303. 区域和检索 - 数组不可变(Easy)

class NumArray:
    def __init__(self, nums: List[int]):
        n = len(nums)
        self.sum = [0] * n
        for i in range(n):
            self.sum[i] = self.sum[i-1] + nums[i]

    def sumRange(self, left: int, right: int) -> int:
        return self.sum[right] - self.sum[left-1] if left > 0 else self.sum[right]

3.2 数组中等差递增子区间的个数

413. 等差数列划分(Medium)

方法一：动态规划
dp[i] 表示以 A[i] 结尾的等差区间的数量；

如果{ A[i-3]，A[i-2]，A[i-1] } 为等差区间，以 A[i-1] 结尾的等差区间数量为 dp[i-1]。并且 A[i]-A[i-1]==A[i-1]-A[i-2]，得出以 A[i] 结尾的等差区间数量为 dp[i]=dp[i-1]+1。

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        vec = [0] * n
        for i in range(2, n):
            if nums[i-1] - nums[i-2] == nums[i] - nums[i-1]:
                vec[i] = vec[i-1] + 1
        return sum(vec)

时间复杂度：O(n)
空间复杂度：O(n)

动态规划的空间优化，计算 dp[i] 时每次只用到 dp[i-1]，所有没有必要使用数组。

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        dp = 0
        res = 0
        for i in range(2, n):
            if nums[i-1] - nums[i-2] == nums[i] - nums[i-1]:
                dp += 1
                res += dp
            else:
                dp = 0
        return res

时间复杂度：O(n)
空间复杂度：O(1)

方法二：用公式计算
从前面的分析可以看出，当出现一个等差区间时，从数组中第三个数开始，以该数结尾的区间数分别为1，2，3，4……，所以可以直接用公式求解。

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        count = 0
        res = 0
        for i in range(2, n):
            if nums[i-1] - nums[i-2] == nums[i] - nums[i-1]:
                count += 1
            else:
                res += (count+1)*count//2
                count = 0
        return res + (count+1)*count//2

4、分割整数

4.1 分割整数的最大乘积

343. 整数拆分(Medium)
子问题：求和为 i 的整数分割后的最大乘积，用 dp[i] 表示
边界条件：dp[1]=1
递推公式：dp[i]=max(dp[i],max(dp[i-j]*j,(i-j)*j));

  • dp[i] 表示本次不分割的最大乘积
  • dp[i-j]*j 表示本次分割出一个 j，剩下的和为 i-j 再分割
  • (i-j)*j 表示本次分割出一个 j，剩下的不分割的最大乘积
class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [1] * (n+1)
        for i in range(2, n+1):
            for j in range(1,  i):
                dp[i] = max(dp[i], dp[i-j] * j, (i-j)*j)
        return dp[n]

4.2 将一个数分解为整数的平方和

279. 完全平方数(Medium)
问题分析：
子问题分解：将 i 分解为整数的平方，最少可以分解为几个数的平方，用 dp[i] 表示。
初始化：dp[i] = i，表示全部分解为 1 的和。
递推条件：dp[i] = min(dp[i], dp[i-j*j]+1) { j>=1 && j*j<=i }

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

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

4.3 分割整数构成字母字符串

91. 解码方法(Medium)

问题分析：
子问题：到第 i 个字符可以解码的总方法，用 dp[i] 表示。
边界条件：dp[0]=1，如果第一个字符为 ‘0’，dp[1]=0，否则为 1。
递推公式：
先看挑出一个字符：

  • 第 i 个字符不是 0（dp[i-1]!=0），一定可以挑出一个字符，dp[i]+=dp[i-1]

再看挑出两个字符：

  • 第 i-1 个字符是 0（dp[i-2] == 0），挑不出两个字符，进行下一轮判断
  • 第 i-1 个字符不是 0，看第 i-1，i 个字符组成的数字，如果小于等于26，表示可以挑出两个字符，dp[i]+=dp[i-2]

其他情况下无法挑出字符，为 0，不予改变。

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

        for i in range(2, n+1):
            if s[i-1] != '0':
                dp[i] += dp[i-1]
            if s[i-2] == '0':
                continue
            tmp = s[i-2] + s[i-1]
            if tmp <= '26':
                dp[i] += dp[i-2]
        return dp[n]

5、最长上升子序列

5.1 最长上升子序列

91. 解码方法(Medium)

方法一：动态规划

找出状态转移方程：
maxLen(k) 表示以 ak 做为“终点”的最长上升子序列的度，那么：

  • 初始状态：maxLen (1) = 1
  • maxLen (k) = max { maxLen (i)：1<= i< k 且 ai< ak 且 k≠1 } + 1
    若找不到这样的 i，则 maxLen (k) = 1

maxLen (k) 的值，就是在 ak 左边，“终点”数值小于 ak，且长度最大的那个上升子序列的长度再加 1。

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * (n+1)
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i+1] = max(dp[i+1], dp[j+1]+1)
        return max(dp)
  • 时间复杂度：O(n2)
  • 空间复杂度：O(n)

5.2 数对可以组成的最长链

646. 最长数对链(Medium)

方法一：贪心
对所有的数对按照第二个数的大小进行排序。第一步选结束数字最小的那个数对。 然后，每步都选和上一个选中的数对不冲突且结束数字最小的那个数。

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        res = 1
        pairs.sort(key=lambda x : x[1])
        tail = pairs[0][1]
        for item in pairs:
            if item[0] > tail:
                res += 1
                tail = item[1]
        return res

方法二：动态规划
对所有的数对按照第一个数的大小进行排序。子问题为数对 pairs[i]（i=1, 2, 3…N）为终点的最长链。a[i] 表示已数对 pairs[i]为终点的链长度。

  • 初始状态：a[i] = 1
  • a[i] = max { a[i], a[j]+1} 0<= j< i 且 pairs[i][0]>pairs[j][1]

再寻找 a[i] 的最大值。

class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs.sort()
        n = len(pairs)
        dp = [1] * (n+1)
        for i in range(1, n):
            for j in range(i):
                if pairs[i][0] > pairs[j][1]:
                    dp[i+1] = max(dp[i+1], dp[j+1] + 1)
        return max(dp)

5.3 最长摆动子序列

376. 摆动序列(Medium)

方法一：动态规划
子问题：求以第 i 个元素结尾的最长摆动子序列，

up[i] 指的是到目前为止所获得的最长摆动子序列的长度，其中第 i 个元素是摆动子序列的最后一个元素并且以上升的摆动结束。
类似地，down[i] 指的是到目前为止获得的最长摆动子序列的长度，其中第 i 个元素作为摆动子序列的最后一个元素并且以下降摆动结束。
边界条件：up[i] = down[i] = 1（每个元素自身都可以作为一个子序列）

递推公式：
up[i] = max(up[i], down[j]+1) (j=0, 1 ,……i-1)
down[i] = max(down[i], up[j]+1) (j=0, 1 ,……i-1)

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        
        up = [1] * n
        down = [1] * n
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    up[i] = max(up[j], down[j] + 1)
                elif nums[i] < nums[j]:
                    down[i] = max(down[j], up[j] + 1)

        return max(max(up), max(down))

时间复杂度：O(n2)
空间复杂度：O(n)

方法二：线性动态规划

子问题：前 i 个元素所组成的最长摆动子序列，

  • 到第 i 个元素，最后一个元素以上升的摆动结束的长度为 up[i]
  • 到第 i 个元素，最后一个元素以下降的摆动结束的长度为 down[i]

边界条件：

  • up[0] = down[0] = 1;

递推公式：文章来源地址https://www.toymoban.com/news/detail-438350.html

  • 如果 nums[i] > nums[i-1]，意味着序列将上摆，前一个序列必然下降，得出：up[i] = down[i-1] + 1, down[i] = down[i−1]；
  • 如果 nums[i] < nums[i-1]，意味着序列将下降，前一个序列必然上摆，得出down[i] = up[i−1]+1, up[i] = up[i-1]；
  • 如果 nums[i] == nums[i-1]，上摆下降序列都不变down[i] = down[i-1]，up[i] = up[i-1]。
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        n = len(nums)
        up = [1] * n
        down = [1] * n
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                up[i] = max(up[i-1], down[i-1] + 1)
                down[i] = down[i-1]
            elif nums[i] < nums[i-1]:
                down[i] = max(down[-1], up[i-1] + 1)
                up[i] = up[i-1]
            else:
                up[i] = up[i-1]
                down[i] = down[i-1]

        return max(up[n-1], down[n-1])

6、最长公共子序列

1143. 最长公共子序列(Medium)

  1. 状态定义

定义 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列。（注：text1[0:i-1] 表示的是 text1 的第 0 个元素到第 i - 1 个元素，两端都包含）

  1. 状态的初始化

当 i = 0 时，dp[0][j] 表示的是 text1 中取空字符串跟 text2 的最长公共子序列，结果肯定为 0。
当 j = 0 时，dp[i][0] 表示的是 text2 中取空字符串跟 text1 的最长公共子序列，结果肯定为 0。
所以，当 i = 0 或者 j = 0 时，dp[i][j] 初始化为 0.

  1. 状态转移方程

当 text1[i - 1] == text2[j - 1] 时，说明两个子字符串的最后一位相等，所以最长公共子序列又增加了 1，所以 dp[i][j] = dp[i - 1][j - 1] + 1。

当 text1[i - 1] != text2[j - 1] 时，说明两个子字符串的最后一位不相等，那么此时的状态 dp[i][j] 应该是 dp[i - 1][j] 和 dp[i][j - 1] 的最大值。

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

        for i in range(1, row+1):
            for j in range(1, col+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[row][col]

7、0-1背包

7.1 将数组分为和相等的两部分

416. 分割等和子集(Medium)

方法一:
问题分解：dp[i][j]表示从前i个数字中取数字，和不超过 j，最大的和是多少。
边界条件：dp[0][j]=0; dp[i][0]=0;
递推公式：dp[i][j] = max( dp[i-1][j], dp[i-1][j-nums[i]]+nums[i] );

dp[i][j]表示前i个数字中取数子，背包容量为 j，可以得到的最大容量是多少，如果 dp[n][sum/2]==sum/2，即背包容量为 sum/2，从所有的数字中选，得到的最大和为 sum/2，说明可以将数组分为和相等的两份。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        total = sum(nums)
        if total % 2:
            return False
        dp = [0] * (total//2 + 1)
        for i in range(n):
            for j in range(total//2, nums[i]-1, -1):
                dp[j] = max(dp[j], dp[j-nums[i]] + nums[i])
        return dp[total//2] == total//2

方法二:

问题分解：dp[i][j]表示从前 i 个数字中取数字，和为 j 是否可行，可行为 true，不可行为 false。
边界条件：dp[i][0]=true;
递推公式：dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)
        total = sum(nums)
        if total % 2:
            return False

        dp = [False] * (total//2 + 1)
        dp[0] = True

        for i in range(n):
            for j in range(total//2, nums[i]-1, -1):
                dp[j] = dp[j] or dp[j-nums[i]]
        return dp[total//2]

7.2 为一组数指定正负号使其和为目标值

494. 目标和(Medium)

将数分为正负两部分，分别为 P 和 N，
sum( P)-sum(N)=target
sum( P)+sum(N)+sum( P)-sum(N)=target+sum( P)-sum(N)
2*sum( P)=target+sum(nums)
问题变为从数组种任意选取数值，使得和为 (target+sum(nums))/2，一共有多少种选法。

问题分解：从前 i 个数字中任意选取，使得和为 j，一共有多少种选法，用 dp[i][j] 表示
边界条件：dp[i][0]=1，dp[0][j]=0 { j=1,2,3……}
递推公式：dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i]]

空间优化，二维数组变为一维数组

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        total = sum(nums)
        if total < target or (total + target) % 2 == 1:
            return 0

        w = (total + target)//2
        if w < 0:
            return 0
        dp = [0] * (w + 1)
        dp[0] = 1
        for _, num in enumerate(nums):
            for j in range(w, num-1, -1):
                dp[j] += dp[j-num]
        
        return dp[w]

7.3 从字符串集合中选尽可能多的字符串并保证0和1个数不超过给定值

474. 一和零(Medium)

问题分析:
可以理解为一个多维费用的 0-1 背包问题，只不过这里有两个背包，分别表示 0 的数量和 1 的数量。从集合中选取字符串，保证所有 0 的数量不大于 m，所有 1 的数量不大于 n，最多可以选多少个字符串。

问题分解：从集合中前 k 个字符串中字符，使得 0 的数量不大于 i，1 的数量不大于 j，最多可以选多少个字符串。用 dp[k][i][j] 表示。
边界条件：dp[k][0][j]=0; dp[k][i][0]=0;
递推公式：dp[k][i][j]=max( dp[k-1][i][j], dp[k-1][i-zero][j-one] ); // zero表示字符串 k 中 0 的个数，one 表示字符串 k 中 1 的个数。

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        Len = len(strs)
        dp = [[[0 for _ in range(n+1)] for _ in range(m+1)] for _ in range(Len+1)]

        for k in range(1, Len+1):
            cnt0 = strs[k-1].count('0')
            cnt1 = strs[k-1].count('1')
            for i in range(m+1):
                for j in range(n+1):
                    dp[k][i][j] = dp[k-1][i][j]
                    if cnt0 <= i and cnt1 <= j:
                        dp[k][i][j] = max(dp[k-1][i][j], dp[k-1][i-cnt0][j-cnt1] + 1)
        
        return dp[Len][m][n]

空间优化，三维数组变为二维数组，逆序遍历

class Solution:
    def findMaxForm(self, strs: List[str], m: int, n: int) -> int:
        dp = [[0 for _ in range(n+1)] for _ in range(m+1)]
        for s in strs:
            cnt0 = s.count('0')
            cnt1 = s.count('1')
            for i in range(m, cnt0-1, -1):
                for j in range(n, cnt1-1, -1):
                    dp[i][j] = max(dp[i][j], dp[i-cnt0][j-cnt1] + 1)
        return dp[m][n]

7.4 用最少的硬币拼出总额

322. 零钱兑换(Medium)
我们采用自下而上的方式进行思考。仍定义 dp[i] 为组成金额 i 所需最少的硬币数量。
初始值：dp[0] = 0
递推条件：dp(i) = min(dp[i], dp[i-j] + 1)
其中 j 代表的是硬币面值

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

7.5 找零钱的组合

8、买卖股票

8.1 需要冷却的股票交易

309. 最佳买卖股票时机含冷冻期(Medium)
解题思路：
定义三种状态

  • nostock：没有股票，可以买进
  • havestock：拥有股票，可以出售
  • cool：正在冷却

更新三种状态

  • 此时是冷却状态，可以是前面就是冷却状态，继续保持，也可以是卖了股票，变成冷却状态 cool = max(cool, havestock + prices[i]);
  • 此时拥有股票，可以是前面就有股票，继续拥有，也可以是从没有股票的状态下买了股票 havestock = max(havestock, nostock - prices[i]);
  • 此时没有股票，可以是前面也没有股票，继续保持，也可以是冷却状态变成没有股票的状态（冷却结束）nostock = max(nostock, cool);
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        nostock = 0
        havestock = -prices[0]
        cool = 0
        
        for price in prices:
            tmp = cool
            cool = max(tmp, havestock+price)
            havestock =max(havestock, nostock-price)
            nostock = max(nostock, tmp)
        return max(nostock, cool)

8.2 收交易费的交易

714. 买卖股票的最佳时机含手续费(Medium)
解题思路：
定义两种状态，买进（buy）和卖出（sell），buy 表示此时买进获得的利润，sell 表示此时卖出得到的利润。

class Solution:
    def maxProfit(self, prices: List[int], fee: int) -> int:
        sell = 0
        buy = -prices[0]
        for price in prices:
            sell = max(sell, buy+price-fee)
            buy = max(buy, sell-price)
        return max(sell, buy)

8.3 最多进行两次交易

123. 买卖股票的最佳时机 III(hard)
解题思路：
定义四种状态：第一次买（buy1）；第一次卖（sell1）；第二次买（buy2）；第二次卖（sell2）

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy1 = -prices[0]
        sell1 = 0
        buy2 = -prices[0]
        sell2 = 0
        for price in prices:
            buy1 = max(buy1, -price)
            sell1 = max(sell1, buy1 + price)
            buy2 = max(buy2, sell1 - price)
            sell2 = max(sell2,buy2 + price)
        return max(sell1, sell2)

8.4 只能进行 k 次的股票交易

188. 买卖股票的最佳时机 IV(hard)
略

最长回文子序列

516. 最长回文子序列(Medium)

  1. 确定状态
    dp[i][j]：以下标 i 为起始点，下标 j 为结束点的子串的最长回文子序列长度。

  2. 状态转移方程
    当 s[i] == s[j] 时，dp[i][j] = dp[i+1][j-1] + 2
    当 s[i] != s[j] 时，dp[i][j] = max(dp[i+1, j], dp[i, j-1])

  3. 算法流程
    初始 dp[][] = 0
    dp[i][i] = 1

  4. 返回：return dp[0][n-1]

从最后一行开始计算，每行从左向右计算

class Solution(object):
    def longestPalindromeSubseq(self, s):
        n = len(s)
        dp = [[0]*n for _ in range(n)]
        for i in range(n):
            dp[i][i] = 1
        for i in range(n-1, -1, -1):
            for j in range(i+1, n):
                if s[i] == s[j]:
                    dp[i][j] = dp[i+1][j-1] + 2
                if s[i] != s[j]:
                    dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        return dp[0][n-1]

交错字符串

97. 交错字符串(Hard)

方法：动态规划

首先如果 len(s1) + len(s2) != len(s3) 返回 False

定义：dp[i][j] 表示 s1 的前 i 个元素和 s2 的前 j 个元素是否能交错组成 s3 的前 i+j 个元素。

边界条件： d[0][0] =True

递推公式：

  • 如果 s1 的第 i 个元素和 s3 的第 i+j 个元素相等，那么 s1 的前 i 个元素和 s2 的前 j 个元素是否能交错组成 s3 的前 i + j 个元素取决于 s1 的前 i-1 个元素和 s2 的前 j 个元素是否能交错组成 s3 的前 i+j-1 个元素，即此时 dp[i][j] 取决于 dp[i-1][j]，在此情况下如果 dp[i-1][j] 为真，则 dp[i][j] 也为真。
  • 同样的，如果 s2 的第 j 个元素和 s3 的第 i + j 个元素相等并且 dp[i][j-1] 为真，则 dp[i][j] 也为真。
  • 于是我们可以推导出这样的动态规划转移方程：
    dp[i][j] = (d[i-1][j] and s1[i-1] == s3[i+j-1]) or (dp[i][j-1] and s2[j-1] ==s3[i+j-1])
class Solution(object):
    def isInterleave(self, s1, s2, s3):
        n1, n2, n3 = len(s1), len(s2), len(s3)
        if n1 + n2 != n3:
            return False
        dp = [[False] * (n2+1) for _ in range(n1 + 1)]
        dp[0][0] = True
        for i in range(n1+1):
            for j in range(n2+1):
                if i > 0:
                    dp[i][j] |= (dp[i-1][j] and s1[i-1] == s3[i+j-1])
                if j > 0:
                    dp[i][j] |= (dp[i][j-1] and s2[j-1] == s3[i+j-1])
        return dp[n1][n2]

到了这里，关于Leetcode题解-算法-动态规划（python版）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 解锁动态规划：从斐波那契到高效算法

    解锁动态规划：从斐波那契到高效算法

    👤作者介绍：10年大厂数据经营分析经验，现任大厂数据部门负责人。 会一些的技术：数据分析、算法、SQL、大数据相关、python 欢迎加入社区：码上找工作 作者专栏每日更新： LeetCode解锁1000题: 打怪升级之旅 python数据分析可视化：企业实战案例 备注说明：方便大家阅读，

    2024年04月15日
    浏览(39)
  • C++算法 —— 动态规划（1）斐波那契数列模型

    C++算法 —— 动态规划（1）斐波那契数列模型

    每一种算法都最好看完第一篇再去找要看的博客，因为这样会帮你梳理好思路，看接下来的博客也就更轻松了。当然，我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤，且最好画图来理解细节，不要怕麻烦。当你开始画图，仔细阅

    2024年02月10日
    浏览(45)

  • 【算法优选】 动态规划之斐波那契数列模型

    动态规划相关题目都可以参考以下五个步骤进行解答： 状态表⽰ 状态转移⽅程 初始化 填表顺序 返回值 后面题的解答思路也将按照这五个步骤进行讲解。 泰波那契序列 Tn 定义如下： T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数 n，请返回第 n 个泰波那契

    2024年02月05日
    浏览(56)
  • LeetCode刷题笔记【29】：动态规划专题-1（斐波那契数、爬楼梯、使用最小花费爬楼梯）

    LeetCode刷题笔记【29】：动态规划专题-1（斐波那契数、爬楼梯、使用最小花费爬楼梯）

    动态规划（DP，Dynamic Programming）。 其解题思路对比 贪心算法的“直接选局部最优然后推导出全局最优” ；倾向于“ 由之前的结果推导得到后续的结果 ”。 很多时候二者具有相似性，不必死扣概念。 动态规划题目的核心是dp数组的概念和构建(递推公式); 所以具体的解题步骤

    2024年02月09日
    浏览(40)

  • 算法刷题Day 38 动态规划理论基础+斐波那契数+爬楼梯

    动态规划的解题步骤： 确定 dp 数组（dp table）以及下标的含义 确定递推公式 dp 数组如何初始化 确定遍历顺序 举例推导 dp 数组 很基础

    2024年02月15日
    浏览(62)

  • Java数据结构与算法：动态规划之斐波那契数列

    大家好，我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编。在这寒冷的季节里，让我们一同探讨Java中的动态规划，重点关注解决问题的经典代表之一——斐波那契数列。 动态规划简介 动态规划是一种解决问题的数学方法，通常用于优化递归算法。它通过将问

    2024年01月22日
    浏览(47)

  • Leetcode题解-算法-动态规划（python版）

    1.1 爬楼梯 70. 爬楼梯(Easy) 走n阶楼梯的方法有两种，1、先走 1 级台阶，再走 n-1 级台阶；2、先走 2 级台阶，再走 n-2 级台阶 f(n) = f(n-1) + f(n-2) 1.2 强盗抢劫 198. 打家劫舍(Medium) 每个房间财产为 nums[0]……nums[n-1]。 假设 0 至 x 间房获得的最大财产为 f(x)。 f(x) = max(f(x-1),f(x-2)+nums[

    2024年02月03日
    浏览(50)

  • 算法Day38 | 动态规划，509. 斐波那契数， 70. 爬楼梯， 746. 使用最小花费爬楼梯

    动态规划是一种解决问题的算法思想。它通常用于优化问题，其中要求找到一个最优解或最大化（最小化）某个目标函数。 动态规划的核心思想是 将问题分解成更小的子问题，并通过存储子问题的解来避免重复计算 。这样，可以通过解决子问题来构建原始问题的解。动态规

    2024年02月09日
    浏览(57)
  • 【LeetCode题目详解】第九章 动态规划part01 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯 （day38补）

    【LeetCode题目详解】第九章 动态规划part01 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯 （day38补）

    斐波那契数  （通常用  F(n) 表示）形成的序列称为 斐波那契数列 。该数列由  0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： 给定  n ，请计算 F(n) 。 示例 1： 示例 2： 示例 3： 提示： 0 = n = 30 斐波那契数列大家应该非常熟悉不过了，非常适合作为动规第

    2024年02月07日
    浏览(46)
  • 算法训练第三十八天|动态规划理论基础、509. 斐波那契数 、70. 爬楼梯 、 746. 使用最小花费爬楼梯

    算法训练第三十八天|动态规划理论基础、509. 斐波那契数 、70. 爬楼梯 、 746. 使用最小花费爬楼梯

    参考：https://programmercarl.com/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html 动态规划是什么 动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。 所以 动态规划中每一个状态一定是由上一个状态推导出来的 ，这一

    2024年02月04日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包