08.动态规划

# `① 子序列&子数组`

# 701.最长递增子序列

300.最长递增子序列 (opens new window)
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度

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

1
2
3

1、python

状态定义：dp[i] 表示从数组 nums 开头到 nums[i] 这个位置，最长的严格递增子序列的长度
状态转移方程： dp[i] = max(dp[i], dp[j] + 1) （条件 nums[j] < nums[i]）
初始状态：dp 数组初始为 [1, 1, 1, 1, 1, 1, 1, 1]，表示每个元素单独作为一个子序列的长度为1
通过逐步更新 dp 数组，最终 dp 变成 [1, 1, 1, 2, 2, 3, 4, 4]，因此最长递增子序列的长度为 4

class Solution:
    def lengthOfLIS(self, nums):
        dp = [1] * len(nums)           # 初始化 每个元素单独作为一个子序列的长度为1
        for i in range(1, len(nums)):  # 每次都比较 0~i-1的值与 nums[i]比较
            for j in range(i):
                if nums[i] > nums[j]:  # nums[i]更大 代表 可以接在 nums[j] 后面
                    dp[i] = max(dp[i], dp[j] + 1)

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


print(Solution().lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]))  # 输出: 4

1
2
3
4
5
6
7
8
9
10
11
12

如何更新dp[i]:
- 我们想要找到 nums[i] 之前的元素中所有比 nums[i] 小的元素 nums[j]（其中 j < i）
- 如果 nums[j] < nums[i]，那么 dp[i] 可以更新为 dp[i] = max(dp[i], dp[j] + 1)
- 表示 nums[i] 可以接在 nums[j] 后面（遍历0~i-1 多有数据即可知道接在哪里最长）

# 702.最长公共子序列

1143.最长公共子序列 (opens new window)
给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度
如果不存在 公共子序列 ，返回 0
由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串

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

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

1
2
3
4
5
6
7

1、Python

状态定义：dp[i][j] 表示字符串 text1 的前 i 个字符和字符串 text2 的前 j 个字符的最长公共子序列的长度
状态转移方程：
- 如果 text1[i-1] == text2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1，表示当前字符匹配，公共子序列长度加 1
- 如果 text1[i-1] != text2[j-1]，则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])，表示字符不匹配，选择之前的较长子序列
初始状态：
- 创建一个大小为 (m+1) x (n+1) 的二维数组 dp，其中所有元素初始化为 0
- 因为空字符串与任何字符串的最长公共子序列长度都是 0，这个数组用于存储子问题的解

时间复杂度: O(m * n)

空间复杂度: O(m * n) 二维数组来存储中间结果

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    # dp[i][j] 表示 text1 前 i 个字符和 text2 前 j 个字符的最长公共子序列的长度
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):         # i指针遍历 text1 字符串
        for j in range(1, n + 1):     # j指针遍历 text2 字符串
            if text1[i - 1] == text2[j - 1]:
                # 如果当前字符相同，取前一状态（对角线）的值加 1
                dp[i][j] = dp[i - 1][j - 1] + 1 
            else:
                # 如果当前字符不同，取 dp[i-1][j] 和 dp[i][j-1] 中的最大值
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[m][n]    # 最终结果位于 dp[m][n]，即为最长公共子序列的长度

print(longestCommonSubsequence("abcde", "ace"))  # 输出: 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 703.最长重复子数组

718.最长重复子数组 (opens new window)
给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度

输入：nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
输出：3
解释：长度最长的公共子数组是 [3,2,1]

1
2
3

1、Python dp

定义一个二维数组 dp，其中 dp[i][j] 表示以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度
初始化：当 i=0 或 j=0 时，dp[i][j] 应为 0，因为空数组不可能有公共子数组
状态转移：如果 nums1[i-1] == nums2[j-1]，那么 dp[i][j] = dp[i-1][j-1] + 1，否则，dp[i][j] = 0
最终结果：遍历整个 dp 数组，找到其中的最大值即为所求的最长公共子数组的长度

class Solution(object):
    def findLength(self, nums1, nums2):
        m, n = len(nums1), len(nums2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        max_len = 0

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # 如果 nums1[i-1] == nums2[j-1]，长度值先更新为 斜对角值+1
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    
                    max_len = max(max_len, dp[i][j]) # 更新最大长度
                else:
                    dp[i][j] = 0 # 否则，dp[i][j] = 0

        # 最终结果：遍历整个 dp 数组，找到其中的最大值即为所求的最长公共子数组的长度
        return max_len

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

以 nums1 = [1, 2, 3, 2, 1] 和 nums2 = [3, 2, 1, 4, 7] 为例，构建 dp 数组如下：

i\j	1	2	3
0	0	0	0
1	0	0	1
2	0	1	0
3	1	0	0
4	0	2	0
5	0	0	3

#

# `② 背包&组合`

# 711.零钱兑换 `最少硬币数`

322.零钱兑换 (opens new window)
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额
计算并返回可以凑成总金额所需的 最少的硬币个数
如果没有任何一种硬币组合能组成总金额，返回 -1
你可以认为每种硬币的数量是无限的

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

输入：coins = [2], amount = 3
输出：-1

输入：coins = [1], amount = 0
输出：0

1
2
3
4
5
6
7
8
9

1、Python

状态定义：我们定义一个一维数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币个数
状态转移方程： dp[i] = min(dp[i], dp[i - coin] + 1)
- dp[i - coin] 是前面的计算结果，代表金额 i - coin 最少用了多少硬币
- +1 是再加上当前硬币 coin，就变成了 i
- min(dp[i], dp[i - coin] + 1) 是找出最优解，确保 dp[i] 存的是最少的硬币数
初始状态：[0, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12]
- dp[i] 表示凑成金额 i 所需的最少硬币数
- dp[0] = 0（金额为 0，不需要硬币）
- 其他 dp[i] 初始化为一个不可能达到的值，通常设置为 amount + 1（这里是 12）
- 确保 min(dp[i], dp[i - coin] + 1) 能正确更新 dp[i]

class Solution:
    def coinChange(self, coins, amount):
        # 初始化 dp 数组，长度为 amount + 1，所有值初始为 amount + 1（表示一个不可能达到的值）
        dp = [amount + 1] * (amount + 1)

        dp[0] = 0  # 当金额为 0 时，所需硬币数为 0
        for i in range(1, amount + 1):  # 遍历从 1 到 amount 的所有金额
            for coin in coins:  # 对于每个金额，遍历所有硬币面值
                if i >= coin:  # 硬币大于当前 i 位置索引不进入循环
                    dp[i] = min(dp[i], dp[i - coin] + 1)  # 更新 dp[i]，取最小值

        # 如果 dp[amount] 仍然为初始值，说明无法凑出这个金额，返回 -1
        return dp[-1] if dp[-1] != amount + 1 else -1

print( Solution().coinChange([1, 2, 5], 11) )  # 输出: 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 712.零钱兑换 II

518.零钱兑换 II (opens new window)
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额
请你计算并返回可以凑成总金额的硬币组合数如果任何硬币组合都无法凑出总金额，返回 0
假设每一种面额的硬币有无限个

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：[1,1,1,1,1], [1,1,1,2], [1,2,2], [5]

1
2
3

1、Python dp

状态定义：我们定义一个一维数组 dp，其中 dp[i] 表示凑成金额 i 的方法数
状态转移方程： dp[i] += dp[i - coin] 表示我们把之前 dp[i - coin] 的组合数加到 dp[i] 中
- 如果我们已经知道了组合成金额 i - coin 的方法数
- 那么，所有组合成金额 i - coin 的方法加上这个硬币 coin 都是组合成金额 i 的有效方法
初始状态：[1, 0, 0, 0, 0, 0]
- dp[0] 为 1，因为凑成金额 0 的唯一方法是使用 0 个硬币
最终 dp = [1, 1, 2, 2, 3, 4]

class Solution:
    def change(self, amount, coins):
        dp = [0] * (amount + 1)    # 创建一个长度为 amount+1 的数组 dp，dp[i] 表示凑成金额 i 的方法数
        dp[0] = 1                  # 初始化 dp[0] 为 1，因为凑成金额 0 的唯一方法是使用 0 个硬币
        for coin in coins:
            for i in range(coin, amount + 1):  # 更新 dp 数组，从当前硬币面值开始到目标金额
                dp[i] += dp[i - coin]  # dp[i] 的新值为 dp[i] 加上 dp[i-coin]，即使用当前硬币前后的组合数
        return dp[amount]              # 返回凑成金额 amount 的所有组合方法数

print(Solution().change(5, [1, 2, 5]))
""" dp变化
[1, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1]  # coin = 1 (只使用 1 硬币时，最多只有1种方法 [1,1,1,1,1])
[1, 1, 2, 2, 3, 3]  # coin = 2 (使用 1 2硬币时，最多有3种方法 [1,1,1,1,1], [1,1,1,2], [1,2,2])
[1, 1, 2, 2, 3, 4]  # coin = 5 (使用 1 2 5硬币时，最多有四种方法 [1,1,1,1,1], [1,1,1,2], [1,2,2], [5])
"""

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 713.分割等和子集

416.分割等和子集 (opens new window)
给你一个只包含正整数的非空数组 nums
请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11]

1
2
3

1、Python dp

状态定义：dp[i] 表示是否可以找到一个子集，其元素之和为 i
状态转移方程：dp[i] = dp[i] or dp[i - num]
- 如果 dp[i - num] 为 True，说明之前的某些数字可以组成和为 i - num 的子集
- 加上当前的 num，就可以组成和为 i 的子集，因此 dp[i] 也应该被设置为 True
初始状态：dp 数组初始为 [True, False, False ...]，表示暂时还不知道是否可以找到对应和的子集

class Solution:
    def canPartition(self, nums):
        total_sum = sum(nums)
        if total_sum % 2 != 0:    # 如果总和是奇数，不可能分成两个相等的子集
            return False

        target = total_sum // 2
        dp = [False] * (target + 1)
        dp[0] = True             # 和为0的子集是存在的，而这个子集就是空集

        for num in nums:
            # list(range(11, 0, -1)) = [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
            for i in range(target, num - 1, -1):  # 需要从后往前更新dp数组，避免重复使用当前数字
                dp[i] = dp[i] or dp[i - num]

        return dp[target]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

推演[1,5,11,5]

# num=1  range(11, 0, -1) = [11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[True, True, False, False, False, False, False, False, False, False, False, False]

# num=5  range(11, 4, -1) = [11, 10, 9, 8, 7, 6, 5]
[True, True, False, False, False, True, True, False, False, False, False, False]

# 11 range(11, 10, -1) = [11]
[True, True, False, False, False, True, True, False, False, False, False, True]

# num=5  range(11, 4, -1) = [11, 10, 9, 8, 7, 6, 5]
[True, True, False, False, False, True, True, False, False, False, True, True]

1
2
3
4
5
6
7
8
9
10
11

#

# `② 背包&组合`

# 721.编辑距离

72.编辑距离 (opens new window)
给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数
你可以对一个单词进行如下三种操作：
- 插入一个字符
- 删除一个字符
- 替换一个字符

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

1
2
3
4
5
6

1、Python dp

初始化边界条件

如果 word1 为空字符串（即 i = 0），则需要将 word2 的前 j 个字符全部插入进去，所需的操作数为 j，即 dp[0][j] = j
如果 word2 为空字符串（即 j = 0），则需要将 word1 的前 i 个字符全部删除，所需的操作数为 i，即 dp[i][0] = i

对于任意的 dp[i][j]，我们有以下几种情况：

字符相等 (word1[i-1] == word2[j-1]):
- 如果 word1 和 word2 的当前字符相同，则不需要额外的操作，因此 dp[i][j] = dp[i-1][j-1]
字符不相等 (word1[i-1] != word2[j-1]):
- 删除操作：从 word1 中删除一个字符，即 dp[i][j] = dp[i-1][j] + 1
- 插入操作：在 word1 中插入一个字符，即 dp[i][j] = dp[i][j-1] + 1
- 替换操作：将 word1 中的一个字符替换为 word2 的字符，即 dp[i][j] = dp[i-1][j-1] + 1

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    
    # 初始化 dp 数组
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 边界条件
    for i in range(1, m + 1):
        dp[i][0] = i  # word1 前 i 个字符转换为空字符串的操作数
    for j in range(1, n + 1):
        dp[0][j] = j  # 空字符串转换为 word2 前 j 个字符的操作数
    
    # 填充 dp 表
    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][j - 1] + 1,  # 插入
                               dp[i - 1][j] + 1,  # 删除
                               dp[i - 1][j - 1] + 1)  # 替换
    
    # 返回最终结果
    return dp[m][n]

# 测试用例
word1 = "horse"
word2 = "ros"
print(minDistance(word1, word2))  # 输出：3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

推演 word1 = "sun"，word2 = "satur"

0）初始化数组
- 第一行 0 1 2 3 4 5 表示word1 为空字符串（即 i = 0），则需要将 word2 的前 j 个字符全部插入进去，所需的操作数为 j
- 第一列 0 1 2 3 表示 word2 为空字符串（即 j = 0），则需要将 word1 的前 i 个字符全部删除，所需的操作数为 i

word1 \ word2    ""   s   a   t   u   r
""               0    1   2   3   4   5
s                1    ?   ?   ?   ?   ?
u                2    ?   ?   ?   ?   ?
n                3    ?   ?   ?   ?   ?

1
2
3
4
5

1）word1[i - 1] == word2[j - 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] + 1,  # 插入
                               dp[i - 1][j] + 1,  # 删除
                               dp[i - 1][j - 1] + 1)  # 替换

1
2
3
4
5
6

#1）计算 dp[1][1]  word1[0] = s 和 word2[0] = s 相等，不需要任何操作
dp[1][1] = dp[0][0] = 0 

# 计算 dp[1][2]  word1[0] = s 和 word2[1] = a 不相等
dp[1][2] = min(
	dp[1][0] + 1,   # 插入(左)
  dp[0][1] + 1,   # 删除（上）
  dp[0][1] + 1,   # 替换（对角）
)
dp[1][2] = min(
	dp[1][0] + 1 = 0 + 1 = 1
  dp[0][1] + 1 = 3 + 1 = 3
  dp[0][1] + 1 = 1 + 1 = 2
)
# 最终 dp[1][2] = 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

word1 \ word2    ""   s   a   t   u   r
""               0    1   2   3   4   5
s                1    0   1   ?   ?   ?
u                2    ?   ?   ?   ?   ?
n                3    ?   ?   ?   ?   ?

1
2
3
4
5

# 722.解码方法

91.解码方法 (opens new window)
一条包含字母 A-Z 的消息通过以下映射进行了编码 "1" -> 'A', ``"26" -> 'Z'`
给你一个只含数字的非空字符串 s ，请计算并返回解码方法的总数
如果没有合法的方式解码整个字符串，返回 0

输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）

1
2
3

1、Python dp

状态定义：dp[i] 表示以 s[i-1]结尾的子字符串的解码方法总数
状态转移方程：
- 如果s[i-1] != '0'，dp[i] = dp[i - 1]
  - 单独解码当前数字，解码方法和 dp[i - 1] 相等
- 如果 s[i-2:i] ，dp[i] += dp[i-2]
  - 这两个字符组成的数字在 10 到 26 之间，且 s[i-2] != '0'，
  - 则dp[i] 方法总数和 dp[i-2] 相等，但是需要累加上面计算结果所以 dp[i] += dp[i-2]
初始状态：dp[0] = 1 表示空字符串有 1 种解码方法
返回结果：dp[n]，即整个字符串的解码方法总数

class Solution:
    def numDecodings(self, s):
        n = len(s)
        # dp[i] 表示以 s[i-1] 结尾的子字符串的解码方法总数
        dp = [1] + [0] * n            # dp[0] = 1 表示空字符串有 1 种解码方法

        for i in range(1, n + 1):
            # 单独解码，单独解码方法数=dp[i - 1] （'0' 不能独立解码）
            if s[i - 1] != '0':
                dp[i] = dp[i - 1]

            # 如果当前字符和前一个字符形成的数字在 10 到 26 之间，且前一个字符不为 '0'
            # 两个数放一起解码：此时 dp[i] = dp[i - 2] 要顾及上面计算结果，所以累加
            if i > 1 and s[i - 2] != '0' and int(s[i - 2:i]) <= 26:
                dp[i] += dp[i - 2]

        return dp[n]

print( Solution().numDecodings("123") )

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

以123为例推演

# 初始化 dp = [1, 0, 0, 0]

# i=1  s[0]='1'，它可以单独解码为 'A'
# dp = [1, 1, 0, 0]
dp[i] = dp[i - 1] => dp[1] += dp[0]  = 1

# i=2  s[1]='2'  它可以单独解码为'B'，并且 s[0:2] = '12' 也可以解码为 'L'
# dp = [1, 1, 2, 0]
因为 s[1] != '0'， 所以 dp[2] = dp[1]， 即 dp[2] = 1  # 单独解码为'B'
因为 10 <= int(s[0:2]) <= 26， 所以 dp[2] += dp[0]，即 dp[2] = 2  # '12' 也可以解码为 'L'

# i=3  s[2]='3'  它可以单独解码为 'C'，并且 s[1:3] = '23' 也可以解码为 'W'
# dp = [1, 1, 2, 3]
因为 s[2] != '0'，所以 dp[3] = dp[2]，即 dp[3] = 2  # 单独解码为 'C'
因为 10 <= int(s[1:3]) <= 26，所以 dp[3] += dp[1]，即 dp[3] = 3  # '23' 也可以解码为 'W'


# dp[3] = 3，表示字符串 "123" 总共有 3 种解码方式：
'1' + '2' + '3' → 'A' + 'B' + 'C'
'12' + '3' → 'L' + 'C'
'1' + '23' → 'A' + 'W'

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

# 723.单词拆分

139.单词拆分 (opens new window)
给你一个字符串 s 和一个字符串列表 wordDict 作为字典如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成

1
2
3

1、Python dp

状态定义：dp[i] 表示字符串 s 中从位置 0 到位置 i-1 的子串是否可以通过字典 wordDict 完全拆分
状态转移方程：if dp[j] and s[j:i] in set_
- 满足 dp[j] 为 True 且 s[j:i] 在字典 wordDict 中
初始状态：dp[0] = True，表示空字符串可以被拆分

class Solution:
    def wordBreak(self, s, wordDict):
        set_ = set(wordDict)        # 转换为集合，{'pen', 'apple'}
        dp = [False] * (len(s) + 1)
        dp[0] = True                # 空字符串可以被拼接

        for i in range(1, len(s) + 1):
            for j in range(i):               # 检查 s[0:j] 中是否存在为True的肯能
                if dp[j] and s[j:i] in set_: # 检查 dp[j] 是否为 True 且 s[j:i] 是否在字典中
                    dp[i] = True
                    break
        return dp[len(s)]
        # dp = [True, False, False, False, False, True, False, False, True, False, False, False, False, True]

print( Solution().wordBreak( "applepenapple", ["apple", "pen"]) )   # True

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最终：dp = [True, False, False, False, False, True, False, False, True, False, False, False, False, True]

# s = "applepenapple", wordDict = ["apple", "pen"]
dp[5] = True  # 因为 `"apple"` 在字典中
dp[8] = True  # 因为 `"pen"` 在字典中，且 dp[5] 为 True
dp[13] = True # 因为 `"apple"` 在字典中，且 `dp[8]` 为 `True`
# 最终，`dp[13]` 为 `True`，因此可以拼接出 `s`

1
2
3
4
5

#

# `④ 其他DP`

# 731.打家劫舍

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

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)  偷窃到的最高金额 = 1 + 3 = 4

1
2
3

1、Python dp

核心思想是对于每个房子，我们有两个选择：偷或者不偷
dp[i] 表示偷到第 i 个房子时能偷到的最大金额
不偷：那么最大金额就是前一个房子偷到的最大金额，即 dp[i-1]
偷：那么最大金额是当前房子的钱加上前前一个房子偷到的最大金额，即 dp[i-2] + nums[i]
边界条件：
- dp[0] = nums[0]，只有一个房子时，偷该房子
- dp[1] = max(nums[0], nums[1])，两个房子时，偷钱更多的那个

class Solution:
    def rob(self, nums):
        n = len(nums)
        if n == 0:
            return 0
        if n == 1:
            return nums[0]
    
        dp = [0] * n         # 创建dp数组，dp[i]表示偷到第i间房子时能获得的最大金额
        dp[0] = nums[0]      # 只有一间房子时，最大金额就是偷这间房子的金额
        dp[1] = max(nums[0], nums[1]) # 有两间房子时，选择金额较大的那一间
        for i in range(2, n):         # 从第3间房子开始遍历到最后一间，更新dp数组
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])  # 不偷（dp[i-1]）偷（dp[i-2] + nums[i]）
            
        return dp[-1]       # 返回dp数组的最后一个值，即偷到最后一间房子时能获得的最大金额

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 732.接雨水

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

1、Python

class Solution:
    def trap(self, height):
        if not height:
            return 0

        n = len(height)
        l_max = [0] * n  # 记录每个位置左侧的最高柱子
        r_max = [0] * n  # 记录每个位置右侧的最高柱子

        # 计算 l_max 数组
        l_max[0] = height[0]  # 最左边的柱子自己就是最高的
        for i in range(1, n):
            l_max[i] = max(l_max[i - 1], height[i])  # 记录当前柱子左侧的最大值

        # 计算 r_max 数组
        r_max[n - 1] = height[n - 1]  # 最右边的柱子自己就是最高的
        for i in range(n - 2, -1, -1):
            r_max[i] = max(r_max[i + 1], height[i])  # 记录当前柱子右侧的最大值

        total = 0
        for i in range(n):
            l_r_min = min(l_max[i], r_max[i])  # 找到当前柱子 左右的最小值
            if height[i] < l_r_min:  # 如果当前柱子比左右的最小值小，接住了雨水
                total += l_r_min - height[i]

        return total  # 返回总的存水量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2、双指针

class Solution:
    def trap(self, height):
        nums = height
        if not nums:
            return 0
        
        l, r = 0, len(nums) - 1
        l_max, r_max = 0, 0         # 初始化左和右最大高度
        s = 0                       # 总共接到的雨水量

        while l <= r:
            if nums[l] <= nums[r]:     # 左侧柱子 小于等于 右侧柱子高度
                if nums[l] >= l_max:   # 左侧柱子 大于等于 左边的最大高度（无雨水）
                    l_max = nums[l]    # 更新左边的最大高度
                else:
                    s += l_max - nums[l]   # 计算当前柱子能够接到的雨水量，并累加
                l += 1
            else:
                if nums[r] >= r_max:  # 右侧柱子 大于等于 右边的最大高度（无雨水）
                    r_max = nums[r]   # 更新右边的最大高度
                else:
                    s += r_max - nums[r] # 计算当前柱子能够接到的雨水量，并累加
                r -= 1
        return s  # 返回计算出的总雨水量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 733.跳跃游戏 II

45.跳跃游戏 II (opens new window)
给定一个长度为 n 的整数数组 nums初始位置为 nums[0]
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处
返回到达 nums[n - 1] 的最小跳跃次数

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2，从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置

1
2
3

1、Python

对于每个位置，计算可以达到的最远位置 tmp_max
如果当前位置是当前跳跃的最远位置 max_，则更新 max_ 为 tmp_max，并增加跳跃次数 steps
如果当前位置 i 等于 max_，我们需要进行一次跳跃，以便扩展跳跃范围，继续前进（否则未到达最远位置不增加跳跃次数）

class Solution:
    def jump(self, nums):
        steps = 0            # 跳跃次数
        max_ = 0             # 当前跳跃能到达的最远位置
        tmp_max = 0          # 遍历过程中能到达的最远位置

        for i in range(len(nums) - 1):
            # 更新当前跳跃范围内能到达的最远位置
            tmp_max = max(nums[i] + i, tmp_max)  # `nums[i] + i` 表示从当前位置 `i` 能跳到的最远位置
            if i == max_:       # 当前位置 i 等于 max_，我们需要进行一次跳跃，以便扩展跳跃范围，继续前进
                max_ = tmp_max  # 更新当前跳跃范围的结束位置
                steps += 1
                if max_ >= len(nums) - 1:  # 如果可以到达最后一个位置，提前结束
                    break
        return steps

print( Solution().jump([3,2,1,3,2,1]) )    # 输出 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

上次更新: 2025/3/25 17:29:52

← 06.回溯算法 11.字符串→

08.动态规划

# ① 子序列&子数组

# 701.最长递增子序列

# 702.最长公共子序列

# 703.最长重复子数组

#

# ② 背包&组合

# 711.零钱兑换 最少硬币数

# 712.零钱兑换 II

# 713.分割等和子集

#

# ② 背包&组合

# 721.编辑距离

# 722.解码方法

# 723.单词拆分

#

# ④ 其他DP

# 731.打家劫舍

# 732.接雨水

# 733.跳跃游戏 II

# `① 子序列&子数组`

# `② 背包&组合`

# 711.零钱兑换 `最少硬币数`

# `② 背包&组合`

# `④ 其他DP`