做公司网站需要准备什么,企业备案网站名称要求,关于学校的网站模板免费下载,网页转app工具动态规划练习题
题目描述
给定两个字符串 text1 和 text2#xff0c;要求返回这两个字符串的最长公共子序列。例如对于字符串 “ABAZDC” 和 “BACBAD”#xff0c;需找出它们最长的公共子序列。子序列是指在不改变其余字符相对位置的情况下#xff0c;从原始字符串中删除…动态规划练习题
题目描述
给定两个字符串 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]解析
动态规划思路本题采用动态规划方法核心是通过分析子问题的解来构建最终问题的解。状态定义定义二维数组 dp[i][j] 表示 text1 的前 i 个字符和 text2 的前 j 个字符的最长公共子序列长度。状态转移方程 当 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 个字符的最长公共子序列。 边界条件dp[0][j] 0 表示 text1 为空字符串时最长公共子序列长度为0dp[i][0] 0 表示 text2 为空字符串时最长公共子序列长度为0 。时间复杂度由于使用了两层嵌套循环遍历两个字符串时间复杂度为 O ( m × n ) O(m \times n) O(m×n)其中 m m m 和 n n n 分别是 text1 和 text2 的长度。空间复杂度使用了一个二维数组 dp 存储中间结果空间复杂度为 O ( m × n ) O(m \times n) O(m×n) 不过可以通过滚动数组优化为 O ( m i n ( m , n ) ) O(min(m, 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解析
动态规划思路本题可采用动态规划的方法求解。动态规划的核心是将原问题分解为多个子问题通过求解子问题并保存结果来避免重复计算最终得到原问题的解。状态定义定义 f(n) 表示爬到第 n 阶楼梯的不同方法数。状态转移方程因为每次可以爬 1 阶或 2 阶所以爬到第 n 阶的方法数等于爬到第 n - 1 阶的方法数加上爬到第 n - 2 阶的方法数即 f(n) f(n - 1) f(n - 2) 。这是一个类似斐波那契数列的递推关系。边界条件当 n 1 时只有一种方法爬 1 阶即 f(1) 1 当 n 2 时有两种方法两次爬 1 阶或一次爬 2 阶 即 f(2) 2 。代码实现细节代码中使用了两个变量 a 和 b 分别表示 f(n - 2) 和 f(n - 1) 通过不断更新这两个变量来计算 f(n) 。循环从 n 2 开始每次迭代更新 a 和 b 的值最终 b 存储的就是爬到第 n 阶的方法数。复杂度分析 时间复杂度代码中只进行了一次循环循环次数为 n - 2 次每次循环的操作都是常数时间的所以时间复杂度为 O ( n ) O(n) O(n) 。空间复杂度只使用了常数个额外变量a 和 b 所以空间复杂度为 O ( 1 ) O(1) O(1) 。 这种空间复杂度为常数的实现方式是对动态规划空间优化后的结果相较于使用数组存储所有子问题结果空间复杂度为 O ( n ) O(n) 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]
解析
动态规划思路采用动态规划来解决此问题。动态规划的关键在于将问题分解为多个子问题并利用子问题的解来构建最终问题的解。状态定义把 triangle[i][j] 看作状态表示从三角形第 i 行第 j 列这个位置到底部的最小路径和。状态转移方程对于第 i 行第 j 列的元素它下一步可以移动到下一行的第 j 列或者第 j 1 列。所以 triangle[i][j] 的最小路径和等于当前位置的值加上下一行相邻两个位置中较小的那个位置的最小路径和即 triangle[i][j] min(triangle[i 1][j], triangle[i 1][j 1]) 。遍历顺序从三角形的倒数第二行开始向上遍历因为最底层的元素到底部的最小路径和就是其自身的值以此为基础向上递推。边界条件最底层的元素不需要进行额外计算其自身值就是从它到底部的最小路径和因为已经是最底层了。复杂度分析 时间复杂度使用了两层嵌套循环外层循环遍历行数内层循环遍历每行的元素总的时间复杂度为 O ( n 2 ) O(n^2) O(n2) 其中 n n n 是三角形的行数。空间复杂度直接在原三角形数组上进行操作没有使用额外的与问题规模相关的空间所以空间复杂度为 O ( 1 ) O(1) 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
解析
动态规划思路本题运用动态规划方法。动态规划的核心是将复杂问题分解为多个相互关联的子问题通过求解子问题并保存结果避免重复计算从而高效地解决原问题。状态定义定义 dp[i] 表示以 nums[i] 结尾的连续子数组的最大和 。状态转移方程对于 dp[i] 它有两种情况。一种是只取 nums[i] 这一个元素作为子数组另一种是将 nums[i] 加入到以 nums[i - 1] 结尾的连续子数组中。所以状态转移方程为 dp[i] max(nums[i], dp[i - 1] nums[i]) 。边界条件当 i 0 时dp[0] nums[0] 因为此时以 nums[0] 结尾的连续子数组就是它本身。求解过程在循环中每计算出一个 dp[i] 就更新 max_sum max_sum 记录的是到当前位置为止所有以不同元素结尾的连续子数组中的最大和。复杂度分析 时间复杂度代码中只有一层循环循环次数为数组的长度 n 每次循环内的操作都是常数时间的所以时间复杂度为 O ( n ) O(n) O(n) 。空间复杂度使用了一个长度为 n 的数组 dp 来保存中间结果所以空间复杂度为 O ( n ) O(n) O(n) 。不过还可以进一步优化将空间复杂度降为 O ( 1 ) O(1) 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 ) O(1) 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
解析
动态规划思路同样采用动态规划策略。由于数组中存在负数负数与负数相乘可能得到更大的乘积所以不能简单地用与最大子数组和类似的方法。需要同时记录以当前元素结尾的最大乘积子数组和最小乘积子数组。状态定义定义 max_ending_here 表示以当前元素 nums[i] 结尾的最大乘积子数组的乘积min_ending_here 表示以当前元素 nums[i] 结尾的最小乘积子数组的乘积 。状态转移方程 对于 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 。 边界条件当 i 0 时max_ending_here min_ending_here nums[0] 。求解过程在循环中每次更新 max_ending_here 和 min_ending_here 后都用 res 记录到当前位置为止的最大乘积最后返回 res 。复杂度分析 时间复杂度只有一层循环循环次数为数组长度 n 每次循环内操作是常数时间所以时间复杂度为 O ( n ) O(n) O(n) 。空间复杂度只使用了几个额外变量空间复杂度为 O ( 1 ) O(1) 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
解析
动态规划思路本题使用动态规划来解决。动态规划的核心在于将问题分解为多个子问题通过求解子问题并保存结果避免重复计算最终得到原问题的解。状态定义定义 dp[i] 表示凑成金额 i 所需的最少硬币个数。状态转移方程对于金额 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) 。边界条件dp[0] 0 表示凑成金额 0 不需要任何硬币。初始化 dp 数组其他元素为 amount 1 这是一个不可能达到的较大值用于后续比较更新。求解过程通过两层循环外层循环遍历从 1 到 amount 的所有金额内层循环遍历所有硬币面额不断更新 dp 数组。最后如果 dp[amount] 仍然是初始的 amount 1 说明无法凑出该金额返回 -1 否则返回 dp[amount] 。复杂度分析 时间复杂度有两层循环外层循环次数为 amount 次内层循环次数为硬币种类数假设为 m 所以时间复杂度为 O ( m × a m o u n t ) O(m \times amount) O(m×amount) 。空间复杂度使用了一个长度为 amount 1 的数组 dp 来保存中间结果所以空间复杂度为 O ( a m o u n t ) O(amount) O(amount) 。
