宁波网站推广优化外包,godaddy 网站怎么建设,南山最专业的网站建设,网络推广教程动态规划 一、动态规划的核心思想二、动态规划的步骤1. 定义状态#xff08;State#xff09;2. 确定状态转移方程#xff08;State Transition Equation#xff09;3. 确定边界条件#xff08;Base Case#xff09;4. 填表#xff08;Table Filling#xff09;或递归计… 动态规划 一、动态规划的核心思想二、动态规划的步骤1. 定义状态State2. 确定状态转移方程State Transition Equation3. 确定边界条件Base Case4. 填表Table Filling或递归计算 三、动态规划的两种常见实现方式1. 自顶向下备忘录法2. 自底向上迭代法 四、动态规划的经典应用1. 背包问题问题描述动态规划解法状态转移方程初始化时间复杂度 代码实现代码解释解释其他优化 2. 最长公共子序列LCS问题描述动态规划解法1. 状态定义2. 状态转移方程3. 边界条件4. 最终结果 动态规划的空间优化代码实现代码解析示例分析时间和空间复杂度 五、动态规划的优化技巧六、总结 一、动态规划的核心思想
动态规划的核心思想是将复杂问题分解为简单的子问题并通过存储子问题的解来避免重复计算从而节省计算时间。动态规划通常适用于满足以下两个条件的问题
最优子结构Optimal Substructure一个问题的最优解可以由其子问题的最优解构成。重叠子问题Overlapping Subproblems问题可以分解为许多重复的子问题而这些子问题的解会被多次利用。 二、动态规划的步骤
解决动态规划问题时通常遵循以下步骤
1. 定义状态State
首先我们需要定义一个状态用来描述问题的子结构。在实际操作中我们通常会定义一个数组或表格来存储子问题的结果。要注意状态的定义应该尽量简单但又能包含足够的信息来从中推导出最终的解。
2. 确定状态转移方程State Transition Equation
状态转移方程是解决动态规划问题的关键它描述了如何从一个子问题的解推导出更大问题的解。状态转移方程通常是递推公式能够根据已解决的子问题来构造当前问题的解。
3. 确定边界条件Base Case
对于最小的子问题也就是递归的基础情形需要明确给出其解这些就是边界条件。在实现时这些边界条件是动态规划算法的起点通常是一些初始值。。
4. 填表Table Filling或递归计算
自底向上通过循环填充表格通常是二维数组或一维数组从最小的子问题开始逐步计算出最终的解。自顶向下通过递归调用子问题并使用备忘录Memoization存储已计算的结果避免重复计算。 三、动态规划的两种常见实现方式
1. 自顶向下备忘录法
在自顶向下的方法中我们通过递归来解决问题每当遇到一个子问题时首先检查它是否已经被计算过。如果已经计算过则直接返回存储的结果如果没有计算过则进行递归计算并将结果存储起来以便以后使用。
# 定义一个计算斐波那契数列的函数使用记忆化递归优化性能
def fibonacci(n, memo{}):# 如果 n 已经在 memo 字典中直接返回 memo[n]避免重复计算if n in memo:return memo[n]# 基本情况斐波那契数列的前两项分别是 0 和 1if n 1:return n# 递归计算第 n 项的值# 第 n 项等于第 (n-1) 项和第 (n-2) 项的和# 并将结果存储到 memo 字典中供后续调用时直接使用memo[n] fibonacci(n-1, memo) fibonacci(n-2, memo)# 返回计算结果return memo[n]# 调用函数计算斐波那契数列的第 10 项
print(fibonacci(10)) # 输出 55这个例子使用了递归且用 memo 字典存储已经计算过的斐波那契数。
2. 自底向上迭代法
自底向上的方法通常通过迭代来逐步填充动态规划表格。首先解决最小的子问题然后逐步解决更大的子问题直到最后得到原问题的解。
# 定义一个计算斐波那契数列的函数使用动态规划DP实现
def fibonacci(n):# 基本情况如果 n 小于等于 1直接返回 n# 因为斐波那契数列的第 0 项是 0第 1 项是 1if n 1:return n# 初始化一个长度为 (n1) 的列表 dp用于存储斐波那契数列的每一项# dp[i] 表示斐波那契数列的第 i 项dp [0] * (n 1)# 显式设置斐波那契数列的第 1 项为 1dp[1] 1# 使用循环从第 2 项开始计算到第 n 项# 每一项 dp[i] 等于前两项 dp[i-1] 和 dp[i-2] 的和for i in range(2, n 1):dp[i] dp[i - 1] dp[i - 2]# 返回斐波那契数列的第 n 项return dp[n]# 调用函数计算斐波那契数列的第 10 项
print(fibonacci(10)) # 输出 55这里使用一个一维数组 dp 存储每个斐波那契数从 dp[0] 到 dp[n]并通过迭代计算出最终的结果。 四、动态规划的经典应用
1. 背包问题
问题描述
给定 n 个物品每个物品有重量和价值。背包的最大容量是 C要求在不超过容量限制的情况下使得背包中的物品总价值最大。
动态规划解法
动态规划的核心思想是使用一个二维数组 dp[i][w] 来表示前 i 个物品放入容量为 w 的背包时的最大价值。
状态转移方程 如果当前物品的重量大于背包的剩余容量那么当前物品不能放入背包。此时最大价值等于不放当前物品时的最大价值 d p [ i ] [ w ] d p [ i − 1 ] [ w ] dp[i][w] dp[i-1][w] dp[i][w]dp[i−1][w] 如果当前物品的重量小于等于背包的剩余容量我们可以选择放入或不放入当前物品 不放入当前物品最大价值为 dp[i-1][w]。放入当前物品时最大价值为 dp[i-1][w - weight[i-1]] value[i-1]即背包容量减去当前物品的重量然后加上当前物品的价值。 所以状态转移方程为 d p [ i ] [ w ] max ( d p [ i − 1 ] [ w ] , d p [ i − 1 ] [ w − w e i g h t [ i − 1 ] ] v a l u e [ i − 1 ] ) dp[i][w] \max(dp[i-1][w], dp[i-1][w - weight[i-1]] value[i-1]) dp[i][w]max(dp[i−1][w],dp[i−1][w−weight[i−1]]value[i−1])
初始化
dp[0][w] 0表示没有物品时不管背包容量如何最大价值都是0。dp[i][0] 0表示背包容量为0时不管有多少物品最大价值都是0。
时间复杂度
由于 dp 数组的大小是 (n1) * (C1)其中 n 是物品的数量C 是背包的容量所以时间复杂度是 O(n * C)。
代码实现
def knapsack(weights, values, C):0-1背包问题的动态规划解法:param weights: 物品的重量列表:param values: 物品的价值列表:param C: 背包的最大容量:return: 背包的最大价值n len(weights) # 物品的数量# 创建一个二维dp数组初始化为0dp [[0] * (C 1) for _ in range(n 1)]# dp[i][w] 表示前i个物品在背包容量为w时的最大价值# 动态规划填充dp数组for i in range(1, n 1): # 遍历每个物品for w in range(1, C 1): # 遍历每个可能的背包容量if weights[i - 1] w:# 如果当前物品的重量小于等于当前背包容量# 选择放入当前物品或者不放入当前物品dp[i][w] max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] values[i - 1])# dp[i - 1][w] 表示不放入当前物品的最大价值# dp[i - 1][w - weights[i - 1]] values[i - 1] 表示放入当前物品的最大价值else:# 当前物品太重不能放入背包dp[i][w] dp[i - 1][w] # 继承上一个物品的最大价值# 返回背包容量为C时的最大价值return dp[n][C]# 示例测试
weights [2, 3, 4, 5] # 物品的重量
values [3, 4, 5, 6] # 物品的价值
C 5 # 背包的最大容量print(knapsack(weights, values, C)) # 输出 7代码解释
初始化 dp 数组dp[i][w] 表示前 i 个物品放入容量为 w 的背包时的最大价值。dp 数组的大小为 (n1) * (C1)初始化为0。填充 dp 数组从 i 1 到 n从 w 1 到 C对于每一个物品我们判断是否能将该物品放入当前容量为 w 的背包。如果能放则选择放与不放之间的最大值。最终结果dp[n][C] 即为考虑所有 n 个物品和容量为 C 时背包的最大价值。
解释
假设有 n 4 个物品分别为
物品1重量 2价值 3物品2重量 3价值 4物品3重量 4价值 5物品4重量 5价值 6
背包的容量为 C 5。
动态规划算法通过逐步选择物品最终得出背包最大价值为 7即选择物品1重量 2价值 3和物品2重量 3价值 4总重量为 5总价值为 7。
其他优化
空间优化可以使用一维数组优化空间从 dp[i][w] 改为 dp[w]每次更新时从右往左更新避免覆盖还未使用的值。
2. 最长公共子序列LCS
最长公共子序列Longest Common Subsequence, LCS是指在给定的两个字符串中找到一个既是这两个字符串的子序列又是它们的最长的一个子序列。子序列的定义是从原字符串中删除某些字符可以不删除任何字符而不改变其他字符的顺序得到的新字符串就是子序列。
问题描述
给定两个字符串 X 和 Y要求找出它们的最长公共子序列的长度。
动态规划解法
用一个二维数组 dp[i][j] 来表示前 i 个字符和前 j 个字符的最长公共子序列的长度。
1. 状态定义
dp[i][j] 表示字符串 X 的前 i 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。
2. 状态转移方程 如果 X[i-1] Y[j-1]这意味着当前两个字符相同当前最长公共子序列长度可以通过将 X[i-1] 或 Y[j-1] 加入到之前的最长公共子序列中得到。此时 d p [ i ] [ j ] d p [ i − 1 ] [ j − 1 ] 1 dp[i][j] dp[i-1][j-1] 1 dp[i][j]dp[i−1][j−1]1 如果 X[i-1] ! Y[j-1]当前两个字符不同意味着我们无法将这两个字符加入到公共子序列中。因此最大值来自于之前的两种选择要么不考虑 X[i-1]要么不考虑 Y[j-1] d p [ i ] [ j ] max ( d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] \max(dp[i-1][j], dp[i][j-1]) dp[i][j]max(dp[i−1][j],dp[i][j−1])
3. 边界条件
dp[0][j] 0当字符串 X 长度为 0 时和任何字符串 Y 的最长公共子序列长度为 0。dp[i][0] 0当字符串 Y 长度为 0 时和任何字符串 X 的最长公共子序列长度为 0。
4. 最终结果
最终的结果即两个字符串的最长公共子序列的长度将存储在 dp[len(X)][len(Y)] 中。
动态规划的空间优化
虽然 dp 数组是二维的但我们每次计算时仅依赖于前一行的值因此可以通过滚动数组将空间复杂度从 O(m * n) 降低为 O(n)。
代码实现
def longestCommonSubsequence(X, Y):动态规划求解最长公共子序列LCS的长度:param X: 第一个字符串:param Y: 第二个字符串:return: LCS 的长度m len(X) # 第一个字符串的长度n len(Y) # 第二个字符串的长度# 初始化 dp 数组dp[i][j] 表示 X[0..i-1] 和 Y[0..j-1] 的 LCS 长度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 X[i - 1] Y[j - 1]: # 如果当前字符相同# LCS 长度等于去掉这两个字符后的 LCS 长度加1dp[i][j] dp[i - 1][j - 1] 1else: # 如果当前字符不同# LCS 长度等于去掉一个字符后的 LCS 长度的最大值dp[i][j] max(dp[i - 1][j], dp[i][j - 1])# 返回 LCS 的长度即 dp[m][n]return dp[m][n]# 示例测试
X ABCBDAB
Y BDCAB
print(longestCommonSubsequence(X, Y)) # 输出 4代码解析
初始化 dp 数组dp[i][j] 表示字符串 X 的前 i 个字符和字符串 Y 的前 j 个字符的最长公共子序列的长度。初始化时dp[i][0] 和 dp[0][j] 都为 0。状态转移我们通过嵌套的 for 循环遍历所有的 i 和 j根据 X[i-1] 和 Y[j-1] 是否相等来更新 dp[i][j]。返回结果最终的最长公共子序列的长度在 dp[m][n] 位置即 X 和 Y 完整字符串的最长公共子序列长度。
示例分析
假设 X ABCBDAB 和 Y BDCAB
比较 X[0] 和 Y[0]A 和 B 不同dp[1][1] 0。比较 X[0] 和 Y[1]A 和 D 不同dp[1][2] 0。比较 X[0] 和 Y[2]A 和 C 不同dp[1][3] 0。比较 X[0] 和 Y[3]A 和 A 相同dp[1][4] 1。比较 X[1] 和 Y[0]B 和 B 相同dp[2][1] 1。比较 X[1] 和 Y[1]B 和 D 不同dp[2][2] 1。 …
最终的 dp 表格会被填充如下仅显示关键部分
BDCABA000011B011112C011112B012223D012223A012233B012234
最终 dp[7][5] 4表示字符串 X ABCBDAB 和 Y BDCAB 的最长公共子序列长度为 4最长公共子序列为 BCAB。
时间和空间复杂度
时间复杂度O(m * n)其中 m 和 n 分别是两个字符串的长度因为我们需要遍历整个 dp 数组。空间复杂度O(m * n)我们需要一个 m * n 的二维数组来存储中间结果。
如果我们需要空间优化可以通过滚动数组的技巧将空间复杂度降为 O(min(m, n))。 五、动态规划的优化技巧 空间优化当动态规划表格很大时可以通过优化空间来减少空间复杂度。例如在计算背包问题时我们只需要保留上一行的结果因此可以将二维数组压缩为一维数组。 状态压缩将多维数组压缩成一维数组尤其是在状态之间仅依赖于前一状态的情况。 六、总结
动态规划是解决具有最优子结构和重叠子问题的优化问题的一种强大工具。通过定义合适的状态和状态转移方程可以将问题的复杂度从指数级降低到多项式级。掌握动态规划的技巧和方法将能有效地解决很多经典的计算机算法问题如背包问题、最长公共子序列、编辑距离等。
