面试算法高频08-动态规划-02

动态规划练习题

题目描述

给定两个字符串 text1 和 text2，要求返回这两个字符串的最长公共子序列。例如对于字符串 “ABAZDC” 和 “BACBAD”，需找出它们最长的公共子序列。子序列是指在不改变其余字符相对位置的情况下，从原始字符串中删除某些字符（也可以不删除）后形成的新字符串。

最优解（Python）

def longestCommonSubsequence(text1, text2):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] + 1else:dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])return dp[m][n]

解析

1. 动态规划思路：本题采用动态规划方法，核心是通过分析子问题的解来构建最终问题的解。
2. 状态定义：定义二维数组 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。
3. 状态转移方程：
   • 当 text1[i - 1] == text2[j - 1] 时，说明当前字符相等，此时 dp[i][j] 等于 dp[i - 1][j - 1] + 1 ，即在前 i - 1 和前 j - 1 个字符最长公共子序列基础上长度加1。
   • 当 text1[i - 1] != text2[j - 1] 时，dp[i][j] 取 dp[i - 1][j] 和 dp[i][j - 1] 中的较大值，因为此时最长公共子序列要么是 text1 前 i - 1 个字符与 text2 前 j 个字符的最长公共子序列，要么是 text1 前 i 个字符与 text2 前 j - 1 个字符的最长公共子序列。
4. 边界条件：dp[0][j] = 0 表示 text1 为空字符串时，最长公共子序列长度为0；dp[i][0] = 0 表示 text2 为空字符串时，最长公共子序列长度为0 。
5. 时间复杂度：由于使用了两层嵌套循环遍历两个字符串，时间复杂度为 $O(m\times n)$，其中 $m$ 和 $n$ 分别是 text1 和 text2 的长度。
6. 空间复杂度：使用了一个二维数组 dp 存储中间结果，空间复杂度为 $O(m\times n)$ ，不过可以通过滚动数组优化为 $O(min(m,n))$ 。

题目描述

题目链接为https://leetcode-cn.com/problems/climbing-stairs/description/ ，假设你正在爬楼梯，需要 n 阶才能到达楼顶。每次你可以爬 1 或 2 个台阶，要求计算有多少种不同的方法可以爬到楼顶 。其中，n 是一个正整数，且满足 1 <= n <= 45 。例如：

• 当输入 n = 2 时，输出为 2，因为有两种方法可以爬到楼顶，分别是 “1 阶 + 1 阶” 和 “2 阶” 。
• 当输入 n = 3 时，输出为 3，因为有三种方法可以爬到楼顶，分别是 “1 阶 + 1 阶 + 1 阶” 、“1 阶 + 2 阶” 、“2 阶 + 1 阶” 。

最优解（Python）

def climbStairs(n):if n <= 2:return na, b = 1, 2for _ in range(2, n):a, b = b, a + breturn b

解析

1. 动态规划思路：本题可采用动态规划的方法求解。动态规划的核心是将原问题分解为多个子问题，通过求解子问题并保存结果来避免重复计算，最终得到原问题的解。
2. 状态定义：定义 f(n) 表示爬到第 n 阶楼梯的不同方法数。
3. 状态转移方程：因为每次可以爬 1 阶或 2 阶，所以爬到第 n 阶的方法数等于爬到第 n - 1 阶的方法数加上爬到第 n - 2 阶的方法数，即 f(n) = f(n - 1) + f(n - 2) 。这是一个类似斐波那契数列的递推关系。
4. 边界条件：当 n = 1 时，只有一种方法（爬 1 阶），即 f(1) = 1 ；当 n = 2 时，有两种方法（两次爬 1 阶或一次爬 2 阶） ，即 f(2) = 2 。
5. 代码实现细节：代码中使用了两个变量 a 和 b 分别表示 f(n - 2) 和 f(n - 1) ，通过不断更新这两个变量来计算 f(n) 。循环从 n = 2 开始，每次迭代更新 a 和 b 的值，最终 b 存储的就是爬到第 n 阶的方法数。
6. 复杂度分析：
   • 时间复杂度：代码中只进行了一次循环，循环次数为 n - 2 次，每次循环的操作都是常数时间的，所以时间复杂度为 $O(n)$ 。
   • 空间复杂度：只使用了常数个额外变量（a 和 b ），所以空间复杂度为 $O(1)$ 。 这种空间复杂度为常数的实现方式是对动态规划空间优化后的结果，相较于使用数组存储所有子问题结果（空间复杂度为 $O(n)$ ）更为高效。

题目描述

题目链接为https://leetcode-cn.com/problems/triangle/description/ ，给定一个三角形 triangle ，它是一个二维列表，其中 triangle[i] 表示三角形第 i 行的数字列表。要求找到从三角形顶部到底部的最小路径和。在每一步只能移动到下一行中相邻的节点上。例如，对于三角形 [[2],[3,4],[6,5,7],[4,1,8,3]] ，从顶部到底部的最小路径和是 11（路径为 2→3→5→1 ）。

最优解（Python）

def minimumTotal(triangle):n = len(triangle)# 从倒数第二行开始向上遍历for i in range(n - 2, -1, -1):for j in range(len(triangle[i])):# 状态转移：选择下方相邻两个数中较小的，加上当前数triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])return triangle[0][0]

解析

1. 动态规划思路：采用动态规划来解决此问题。动态规划的关键在于将问题分解为多个子问题，并利用子问题的解来构建最终问题的解。
2. 状态定义：把 triangle[i][j] 看作状态，表示从三角形第 i 行第 j 列这个位置到底部的最小路径和。
3. 状态转移方程：对于第 i 行第 j 列的元素，它下一步可以移动到下一行的第 j 列或者第 j + 1 列。所以 triangle[i][j] 的最小路径和等于当前位置的值加上下一行相邻两个位置中较小的那个位置的最小路径和，即 triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1]) 。
4. 遍历顺序：从三角形的倒数第二行开始向上遍历，因为最底层的元素到底部的最小路径和就是其自身的值，以此为基础向上递推。
5. 边界条件：最底层的元素不需要进行额外计算，其自身值就是从它到底部的最小路径和（因为已经是最底层了）。
6. 复杂度分析：
   • 时间复杂度：使用了两层嵌套循环，外层循环遍历行数，内层循环遍历每行的元素，总的时间复杂度为 $O(n^2)$ ，其中 $n$ 是三角形的行数。
   • 空间复杂度：直接在原三角形数组上进行操作，没有使用额外的与问题规模相关的空间，所以空间复杂度为 $O(1)$ 。 这种在原数据结构上直接修改来保存中间结果的方式，有效避免了额外的空间开销。

题目描述

链接：https://leetcode-cn.com/problems/maximum-subarray/ 。

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。例如，输入 nums = [-2,1,-3,4,-1,2,1,-5,4] ，输出为 6 ，因为连续子数组 [4,-1,2,1] 的和最大，为 6 。

最优解（Python）

def maxSubArray(nums):n = len(nums)if n == 0:return 0dp = [0] * ndp[0] = nums[0]max_sum = dp[0]for i in range(1, n):dp[i] = max(nums[i], dp[i - 1] + nums[i])max_sum = max(max_sum, dp[i])return max_sum

解析

1. 动态规划思路：本题运用动态规划方法。动态规划的核心是将复杂问题分解为多个相互关联的子问题，通过求解子问题并保存结果，避免重复计算，从而高效地解决原问题。
2. 状态定义：定义 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和 。
3. 状态转移方程：对于 dp[i] ，它有两种情况。一种是只取 nums[i] 这一个元素作为子数组，另一种是将 nums[i] 加入到以 nums[i - 1] 结尾的连续子数组中。所以状态转移方程为 dp[i] = max(nums[i], dp[i - 1] + nums[i]) 。
4. 边界条件：当 i = 0 时，dp[0] = nums[0] ，因为此时以 nums[0] 结尾的连续子数组就是它本身。
5. 求解过程：在循环中，每计算出一个 dp[i] ，就更新 max_sum ，max_sum 记录的是到当前位置为止，所有以不同元素结尾的连续子数组中的最大和。
6. 复杂度分析：
   • 时间复杂度：代码中只有一层循环，循环次数为数组的长度 n ，每次循环内的操作都是常数时间的，所以时间复杂度为 $O(n)$ 。
   • 空间复杂度：使用了一个长度为 n 的数组 dp 来保存中间结果，所以空间复杂度为 $O(n)$ 。不过，还可以进一步优化，将空间复杂度降为 $O(1)$ ，即不使用 dp 数组，而是用一个变量来记录以当前元素结尾的最大子数组和。优化后的代码如下：

def maxSubArray(nums):n = len(nums)if n == 0:return 0cur_sum = nums[0]max_sum = nums[0]for i in range(1, n):cur_sum = max(nums[i], cur_sum + nums[i])max_sum = max(max_sum, cur_sum)return max_sum

此时，只使用了几个额外的变量，空间复杂度为 $O(1)$ 。

题目描述（另一题，链接：https://leetcode-cn.com/problems/maximum-product-subarray/description/ ）

给定一个整数数组 nums ，找出一个乘积最大的连续子数组。子数组最少包含一个元素。例如，输入 nums = [2,3,-2,4] ，输出为 6 ，因为子数组 [2,3] 有最大乘积 6 。

最优解（Python）

def maxProduct(nums):n = len(nums)if n == 0:return 0max_ending_here = min_ending_here = res = nums[0]for i in range(1, n):# 暂存当前的最大值，用于计算新的最小值temp_max = max_ending_heremax_ending_here = max(nums[i], max_ending_here * nums[i], min_ending_here * nums[i])min_ending_here = min(nums[i], temp_max * nums[i], min_ending_here * nums[i])res = max(res, max_ending_here)return res

解析

1. 动态规划思路：同样采用动态规划策略。由于数组中存在负数，负数与负数相乘可能得到更大的乘积，所以不能简单地用与最大子数组和类似的方法。需要同时记录以当前元素结尾的最大乘积子数组和最小乘积子数组。
2. 状态定义：定义 max_ending_here 表示以当前元素 nums[i] 结尾的最大乘积子数组的乘积，min_ending_here 表示以当前元素 nums[i] 结尾的最小乘积子数组的乘积 。
3. 状态转移方程：
   • 对于 max_ending_here ，它的取值可能是当前元素 nums[i] ，也可能是当前元素与之前的 max_ending_here 相乘，还可能是当前元素与之前的 min_ending_here 相乘（因为负负得正，可能得到更大的值），即 max_ending_here = max(nums[i], max_ending_here * nums[i], min_ending_here * nums[i]) 。
   • 对于 min_ending_here ，它的取值可能是当前元素 nums[i] ，也可能是当前元素与之前的 max_ending_here 相乘（得到较小的值），还可能是当前元素与之前的 min_ending_here 相乘，即 min_ending_here = min(nums[i], temp_max * nums[i], min_ending_here * nums[i]) 。这里的 temp_max 是暂存的上一轮的 max_ending_here ，用于计算新的 min_ending_here 。
4. 边界条件：当 i = 0 时，max_ending_here = min_ending_here = nums[0] 。
5. 求解过程：在循环中，每次更新 max_ending_here 和 min_ending_here 后，都用 res 记录到当前位置为止的最大乘积，最后返回 res 。
6. 复杂度分析：
   • 时间复杂度：只有一层循环，循环次数为数组长度 n ，每次循环内操作是常数时间，所以时间复杂度为 $O(n)$ 。
   • 空间复杂度：只使用了几个额外变量，空间复杂度为 $O(1)$ 。

题目描述

题目链接为https://leetcode-cn.com/problems/coin-change/description/ 。给定不同面额的硬币 coins 列表和一个总金额 amount ，编写一个函数来计算可以凑成总金额所需的最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。假设每种硬币的数量是无限的。例如：

• 输入 coins = [1, 2, 5] ，amount = 11 ，输出为 3 ，因为 11 = 5 + 5 + 1 ，最少需要 3 枚硬币。
• 输入 coins = [2] ，amount = 3 ，输出为 -1 ，因为无法用面额为 2 的硬币凑出金额 3 。

最优解（Python）

def coinChange(coins, amount):dp = [amount + 1] * (amount + 1)dp[0] = 0for i in range(1, amount + 1):for coin in coins:if coin <= i:dp[i] = min(dp[i], dp[i - coin] + 1)return dp[amount] if dp[amount] != amount + 1 else -1

解析

1. 动态规划思路：本题使用动态规划来解决。动态规划的核心在于将问题分解为多个子问题，通过求解子问题并保存结果，避免重复计算，最终得到原问题的解。
2. 状态定义：定义 dp[i] 表示凑成金额 i 所需的最少硬币个数。
3. 状态转移方程：对于金额 i ，遍历所有硬币面额 coin ，如果 coin <= i ，那么 dp[i] 可以由 dp[i - coin] + 1 得到（dp[i - coin] 是凑成金额 i - coin 所需的最少硬币个数，加上一枚面额为 coin 的硬币就可以凑成金额 i ），并且取 dp[i] 和 dp[i - coin] + 1 中的较小值，即 dp[i] = min(dp[i], dp[i - coin] + 1) 。
4. 边界条件：dp[0] = 0 ，表示凑成金额 0 不需要任何硬币。初始化 dp 数组其他元素为 amount + 1 ，这是一个不可能达到的较大值，用于后续比较更新。
5. 求解过程：通过两层循环，外层循环遍历从 1 到 amount 的所有金额，内层循环遍历所有硬币面额，不断更新 dp 数组。最后，如果 dp[amount] 仍然是初始的 amount + 1 ，说明无法凑出该金额，返回 -1 ；否则返回 dp[amount] 。
6. 复杂度分析：
   • 时间复杂度：有两层循环，外层循环次数为 amount 次，内层循环次数为硬币种类数（假设为 m ），所以时间复杂度为 $O(m\times amount)$ 。
   • 空间复杂度：使用了一个长度为 amount + 1 的数组 dp 来保存中间结果，所以空间复杂度为 $O(amount)$ 。