python算法和数据结构刷题[5]：动态规划

动态规划（Dynamic Programming, DP）是一种算法思想，用于解决具有最优子结构的问题。它通过将大问题分解为小问题，并找到这些小问题的最优解，从而得到整个问题的最优解。动态规划与分治法相似，但区别在于动态规划的子问题通常不是相互独立的。

动态规划的核心是解决重复子问题。例如，斐波那

契数列问题，可以通过递归实现，但效率低下，因为会有重复计算。动态规划通过存储已解决的子问题的答案，避免重复计算，从而提高效率。这种方法需要额外的存储空间，是一种空间换时间的策略。

如果一个问题，可以把所有可能的答案穷举出来，并且穷举出来后，发现存在重叠子问题，就可以考虑使用动态规划。

单维动态规划

斐波那契数列

def fibonacci(n):
    # 如果n小于等于1，直接返回n
    if n <= 1:
        return n
    
    # 初始化dp数组，用于存储从0到n的斐波那契数
    dp = [0] * (n + 1)
    dp[1] = 1  # 斐波那契数列的第二个数是1

    # 使用动态规划填充dp数组
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    # 返回第n个斐波那契数
    return dp[n]

# 测试代码
print(fibonacci(0))  # 输出 0
print(fibonacci(1))  # 输出 1
print(fibonacci(2))  # 输出 1
print(fibonacci(3))  # 输出 2
print(fibonacci(4))  # 输出 3
print(fibonacci(5))  # 输出 5
print(fibonacci(6))  # 输出 8
print(fibonacci(7))  # 输出 13

70. 爬楼梯 - 力扣（LeetCode）

到达第 n 个台阶的方法数等于到达第 n-1 个台阶和第 n-2 个台阶的方法数之和

class Solution:
    def climbStairs(self, n: int) -> int:
        f = [0] * (n + 1)
        f[0] = f[1] = 1
        for i in range(2, n + 1):
            f[i] = f[i - 1] + f[i - 2]
        return f[n]

118. 杨辉三角 - 力扣（LeetCode）

给出一个整数输出杨辉三角

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

        res = []
        for i in range(numRows):
            for j in range(i):
                if i != 0 and j != 0:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
            res.append(dp[i])

        return res

322. 零钱兑换 - 力扣（LeetCode）

背包问题：背包问题通常描述为：给定一组物品，每个物品有一定的价值（value）和重量（weight），需要从中选择一些物品放入一个给定容量的背包中，使得放入背包的物品的总价值最大，同时不超过背包的容量。

完全背包问题

返回构成该金额所需的最少硬币数量。如果该金额无法通过硬币的任何组合来弥补，则返回。-1

def coinChange(coins, amount):
    # 创建一个数组，长度为 amount + 1，初始值为 amount + 1
    dp = [amount + 1] * (amount + 1)
    # 金额为0时，需要0个硬币
    dp[0] = 0
    
    # 遍历每个金额
    for a in range(1, amount + 1):
        # 遍历每种硬币
        for coin in coins:
            # 如果当前硬币面额小于等于当前金额
            if coin <= a:
                # 更新 dp[a] 为使用当前硬币后的最少硬币数量
                dp[a] = min(dp[a], dp[a - coin] + 1)
    
    # 如果 dp[amount] 还是初始值，则返回 -1，否则返回 dp[amount]
    return dp[amount] if dp[amount] != amount + 1 else -1

# 示例
coins = [1, 2, 5]
amount = 11
print(coinChange(coins, amount))  # 输出应该是 3

279. 完全平方数 - 力扣（LeetCode）

完全背包问题

def numSquares(n):
    # 创建一个数组来存储每个数字的最小完全平方数个数，初始值为0
    dp = [0] * (n + 1)#，用于存储每个数字 i 可以表示为完全平方数之和的最小数量。    
    # 初始化dp数组，每个位置初始为最大值
    for i in range(1, n + 1):
        dp[i] = i  # 最坏的情况是 i 个 1 的平方
    
    # 遍历每个数字，更新其最小完全平方数个数
    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
    
    # 返回n的最小完全平方数个数
    return dp[n]

# 示例
print(numSquares(12))  # 输出应为 3
print(numSquares(13))  # 输出应为 2，因为 13 = 4 + 9

198. 打家劫舍 - 力扣（LeetCode）

def rob(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    dp = [0] * len(nums)
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, len(nums)):
        dp[i] = max(dp[i-1], dp[i-2] + nums[i])
    return dp[-1]

# 示例
nums = [2, 7, 9, 3, 1]
print(rob(nums))  # 输出应该是 12，因为抢第 0、2、4 间房子（2+9+1）

139. 单词拆分 - 力扣（LeetCode）

def wordBreak(s, wordDict):
    # 首先创建一个布尔数组 dp，长度为字符串长度加一，初始化所有值为 False
    dp = [False] * (len(s) + 1)
    # dp[i] 将表示 s 的前 i 个字符是否可以被成功分割
    dp[0] = True  # 空字符串可以被成功分割

    # 遍历字符串的每一个字符
    for i in range(1, len(s) + 1):
        # 对于每一个可能的结束位置 i，检查所有可能的开始位置 j
        for j in range(i):
            # 如果 dp[j] 为 True，且 s[j:i] 在字典中，那么 dp[i] 也为 True
            if dp[j] and s[j:i] in wordDict:
                dp[i] = True
                break  # 找到一个有效的分割就跳出内层循环

    # 返回 dp[len(s)]，它表示整个字符串是否可以被成功分割
    return dp[len(s)]

# 示例用法
swordDict = ["apple", "pen", "applepen", "pine", "pineapple"]
s = "pineapplepenapple"
print(wordBreak(s, swordDict))  # 应该返回 True

300. 最长递增子序列 - 力扣（LeetCode）

最长递增子序列：可以不连续但是前后相对顺序不变

def lengthOfLIS(nums):
    if not nums:
        return 0

    # 初始化一个数组 dp，长度与输入数组相同，所有元素初始为 1
    # dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度
    dp = [1] * len(nums)

    # 遍历数组，计算每个位置的最长递增子序列长度
    for i in range(1, len(nums)):
        for j in range(i):
            # 如果当前元素 nums[i] 大于之前的元素 nums[j]
            # 并且以 nums[i] 结尾的子序列长度可以增加
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)

    # 返回 dp 数组中的最大值，即为最长递增子序列的长度
    return max(dp)

# 示例用法
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(lengthOfLIS(nums))  # 输出应该是 4，因为最长递增子序列是 [2, 3, 7, 101]

重点：如果 nums[i] 大于 nums[j]，那么我们可以将 nums[i] 添加到以 nums[j] 结尾的递增子序列中，从而形成一个更长的递增子序列。

152. 乘积最大子数组 - 力扣（LeetCode）

最大乘积子数组问题是指在一个整数数组中找到一个连续的子数组（至少包含一个数），使得这个子数组中所有数的乘积是最大的。

tmp = imax;
imax = imin;
imin = tmp;

def maxProduct(nums):
    # 初始化最大乘积、当前最大乘积和当前最小乘积
    max_so_far = nums[0]
    min_so_far = nums[0]
    result = nums[0]
    
    # 遍历数组，从第二个元素开始
    for i in range(1, len(nums)):
        # 如果当前元素是负数，那么最大乘积和最小乘积会交换
        if nums[i] < 0:
            max_so_far, min_so_far = min_so_far, max_so_far
        
        # 更新当前最大乘积和最小乘积
        max_so_far = max(nums[i], max_so_far * nums[i])
        min_so_far = min(nums[i], min_so_far * nums[i])
        
        # 更新结果为最大乘积
        result = max(result, max_so_far)
    
    return result

# 示例
nums = [2, 3, -2, 4]
print(maxProduct(nums))  # 输出: 6

416. 分割等和子集 - 力扣（LeetCode）

给定一个整数数组，如果您可以将数组划分为两个子集，使得两个子集中的元素之和相等，则 返回。

01背包问题

def canPartition(nums):
    total_sum = sum(nums)
    # 如果总和是奇数，直接返回 False
    if total_sum % 2 != 0:
        return False
    
    target = total_sum // 2
    dp = [False] * (target + 1)
    dp[0] = True  # 0 总是可以达成，不选择任何元素即可
    
    # 遍历所有物品（数组中的数字）
    for num in nums:
        # 这里必须从 target 递减到 num，以防止一个物品被重复使用
        for j in range(target, num - 1, -1):
            # 如果 dp[j - num] 是 True，则 dp[j] 也应该是 True
            dp[j] = dp[j] or dp[j - num]
    
    # dp[target] 表示是否可以从数组中选取一些数字，使得这些数字的总和等于 target
    return dp[target]

# 示例
nums = [1, 5, 11, 5]
print(canPartition(nums))  # 输出: True

32. 最长有效括号 - 力扣（LeetCode）

当前字符是 ) 并且前一个字符是 (，当前字符是 ) 并且前一个字符也是 )：s = "()(())"

def longest_valid_parentheses(s):
    n = len(s)
    if n == 0:
        return 0

    # dp[i] 表示以 s[i] 结尾的最长有效括号的长度
    dp = [0] * n
    max_len = 0

    for i in range(1, n):
        if s[i] == ')':
            # 如果前一个字符是'('，则可以形成一个有效的括号对
            if s[i - 1] == '(':
                dp[i] = (dp[i - 2] if i >= 2 else 0) + 2
            # 如果前一个字符是')'，并且前面的有效括号长度为 dp[i - 1]
            # 并且 dp[i - 1] 前面的字符是'('，则可以扩展有效括号长度
            elif i - dp[i - 1] > 0 and s[i - dp[i - 1] - 1] == '(':
                dp[i] = dp[i - 1] + (dp[i - dp[i - 1] - 2] if i - dp[i - 1] >= 2 else 0) + 2
            max_len = max(max_len, dp[i])

    return max_len

# 示例
print(longest_valid_parentheses("(()"))  # 输出 2
print(longest_valid_parentheses(")()())"))  # 输出 4

多维动态规划

62. 不同路径 - 力扣（LeetCode）

与杨辉三角和爬楼梯类似

空间复杂度：2n

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        pre = [1] * n
        cur = [1] * n
        for i in range(1, m):
            for j in range(1, n):
                cur[j] = pre[j] + cur[j-1]
            pre = cur[:]
        return pre[-1]

64. 最小路径和 - 力扣（LeetCode）

向下或向右移动从左上角到右下角的最小路径和

到达每个单元格 (i, j) 的最小路径和可以由到达其上方单元格 (i-1, j) 和左方单元格 (i, j-1) 的最小路径和推导出来。

dp[i][j] 表示到达单元格 (i, j) 的最小路径和，到达 (i, j) 的最小路径和等于到达其上方和左方单元格的最小路径和中的较小者，再加上当前单元格的值。

def min_path_sum(grid):
    if not grid or not grid[0]:
        return 0
    
    m, n = len(grid), 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]
    
    # 填充dp数组剩余部分
    for i in range(1, m):
        for j in range(1, n):
            # dp[i][j]可以从上方(dp[i-1][j])或左方(dp[i][j-1])到达，
            # 所以我们取两者的最小值，并加上当前格子的值。
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
    
    # 右下角的格子将包含从左上角到右下角的最小路径和
    return dp[m - 1][n - 1]

5. 最长回文子串 - 力扣（LeetCode）

记录字符串中每对字符之间是否形成回文子串

def longest_palindromic_substring(s):
    n = len(s)
    if n == 0:
        return ""
    
    # 初始化一个二维数组，用于存储子串是否为回文
    dp = [[False] * n for _ in range(n)]
    start = 0  # 最长回文子串的起始位置
    max_length = 1  # 最长回文子串的长度

    # 所有长度为1的子串都是回文
    for i in range(n):
        dp[i][i] = True

    # 检查长度为2的子串是否为回文
    for i in range(n - 1):
        if s[i] == s[i + 1]:
            dp[i][i + 1] = True
            start = i
            max_length = 2

    # 检查长度大于2的子串
    for length in range(3, n + 1):  # 子串长度从3开始递增
        for i in range(n - length + 1):
            j = i + length - 1  # 子串的结束位置
            # 检查子串s[i:j+1]是否为回文
            if s[i] == s[j] and dp[i + 1][j - 1]:
                dp[i][j] = True
                start = i
                max_length = length

    # 返回最长回文子串
    return s[start:start + max_length]

# 示例使用
s = "babad"
print(longest_palindromic_substring(s))  # 输出可能是"bab"或"aba"

1143. 最长公共子序列 - 力扣（LeetCode）

子序列可以是不连续的；子数组（子字符串）需要是连续的。

def longest_common_subsequence(text1, text2):
    # 获取两个字符串的长度
    m, n = len(text1), len(text2)
    
    # 初始化一个二维数组 dp，用于存储子问题的解
    # dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列的长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 填充 dp 数组
    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], dp[i - 1][j - 1])
    
    # dp[m][n] 即为两个字符串的最长公共子序列的长度
    return dp[m][n]

# 测试用例
text1 = "abcde"
text2 = "ace"
# 测试结果
print(longest_common_subsequence(text1, text2))

72. 编辑距离 - 力扣（LeetCode）

定两个字符串和，返回将 word1 转换为 word2 所需的最小步数

def minDistance(word1, word2):
    # 创建一个矩阵来存储子问题的解
    dp = [[0 for x in range(len(word2) + 1)] for x in range(len(word1) + 1)]

    # 初始化矩阵的第一行和第一列
    for i in range(len(word1) + 1):
        dp[i][0] = i
    for j in range(len(word2) + 1):
        dp[0][j] = j

    # 填充dp矩阵
    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:
                # 如果字符不同，取插入、删除、替换三者的最小值加1
                dp[i][j] = 1 + min(dp[i - 1][j],    # 删除
                                   dp[i][j - 1],    # 插入
                                   dp[i - 1][j - 1] # 替换
                                  )

    # dp矩阵的最后一个元素即为编辑距离
    return dp[len(word1)][len(word2)]

# 示例使用
word1 = "horse"
word2 = "ros"
print(minDistance(word1, word2))  # 输出应该是3，因为"horse" -> "ros"需要3步：h -> r, o ->