动态规划（Dynamic Programming，简称 DP）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式来求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
工作原理：
动态规划的工作原理基于两个核心概念：
- 重叠子问题：在求解问题的过程中，有些子问题可能会被重复计算多次。动态规划通过保存子问题的解，避免了这些重复计算。
- 最优子结构：如果问题的最优解可以由其子问题的最优解有效地构造出来，那么该问题就具有最优子结构性质。
动态规划通常包含以下步骤：
- 定义状态：描述问题的子结构，即子问题的解。
- 状态转移方程：描述如何从子问题的解构造出原问题的解。
- 初始化：为最小的子问题设置初始值。
- 计算：按照某种顺序（通常是从最小子问题到最大子问题）计算所有子问题的解。
- 构造解：使用计算出的子问题的解来构造原问题的解。
实现方式：
动态规划的实现方式通常包括自底向上和带备忘录的自顶向下两种。
- 自底向上：从最小的子问题开始，逐步计算更大子问题的解，直到求解出原问题的解。这种方式通常使用表格或数组来保存子问题的解。
- 带备忘录的自顶向下：从原问题开始，递归地求解子问题，并在求解过程中将子问题的解保存在备忘录中，以避免重复计算。
应用场景：
动态规划在许多领域都有广泛的应用，包括背包问题、最短路径问题、最长公共子序列问题、编辑距离问题、资源分配问题等。
代码实例：
以经典的0-1背包问题为例，下面是使用动态规划求解0-1背包问题的Python代码：
python复制代码
def knapsack(values, weights, capacity): | |
n = len(values) | |
dp = [[0 for _ in range(capacity + 1)] for _ in range(n + 1)] | |
for i in range(1, n + 1): | |
for w in range(1, capacity + 1): | |
if weights[i - 1] <= w: | |
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]) | |
else: | |
dp[i][w] = dp[i - 1][w] | |
return dp[n][capacity] | |
# 示例 | |
values = [60, 100, 120] | |
weights = [10, 20, 30] | |
capacity = 50 | |
print(knapsack(values, weights, capacity)) # 输出：220 |
在这个例子中，values数组表示每个物品的价值，weights数组表示每个物品的重量，capacity表示背包的容量。dp[i][w]表示考虑前i个物品，在背包容量为w的情况下能够得到的最大价值。通过填充这个二维数组，我们可以得到原问题的解。
带备忘录的自底向上方法以及代码实例
带备忘录的自底向上方法结合了自底向上和递归两种策略。它首先通过递归地求解子问题来构建问题的解空间，但为了避免重复计算，它使用一个“备忘录”或称为“查找表”来存储已经计算过的子问题的解。这样，当再次遇到相同的子问题时，可以直接从备忘录中查找结果，而不是重新计算。
这种方法的优势在于它结合了递归的清晰性和自底向上的效率。递归使得代码更易于理解和编写，而备忘录则确保了计算的高效性，避免了不必要的重复工作。
下面是一个使用带备忘录的自底向上方法解决0-1背包问题的Python代码实例：
python复制代码
def knapsack_memoization(values, weights, capacity): | |
memo = [[None] * (capacity + 1) for _ in range(len(values) + 1)] | |
def dp(i, w): | |
# 如果当前子问题的解已经在备忘录中，则直接返回 | |
if memo[i][w] is not None: | |
return memo[i][w] | |
# 递归的基本情况 | |
if i == 0 or w == 0: | |
return 0 | |
# 如果当前物品重量大于背包容量，则不考虑该物品 | |
if weights[i - 1] > w: | |
memo[i][w] = dp(i - 1, w) | |
else: | |
# 否则，考虑选择当前物品或不选择当前物品两种情况中的较大值 | |
memo[i][w] = max(dp(i - 1, w), values[i - 1] + dp(i - 1, w - weights[i - 1])) | |
return memo[i][w] | |
# 调用递归函数，求解原问题 | |
return dp(len(values), capacity) | |
# 示例 | |
values = [60, 100, 120] | |
weights = [10, 20, 30] | |
capacity = 50 | |
print(knapsack_memoization(values, weights, capacity)) # 输出：220 |
在这个例子中，memo数组就是我们的备忘录，用于存储子问题的解。dp函数是一个递归函数，它首先检查备忘录中是否已经存在当前子问题的解。如果存在，则直接返回该解；如果不存在，则递归地计算子问题的解，并将结果存储在备忘录中。这样，当相同的子问题再次被调用时，就可以直接从备忘录中取得结果，避免重复计算。
注意，虽然这种方法在概念上使用了递归，但实际上它是通过自底向上的方式填充备忘录的，因此避免了递归的深度限制，并且在实际执行时通常比纯递归方法更高效。
标签：场景,capacity,问题,备忘录,values,原理,动态,weights,dp From： https://blog.csdn.net/qq_24373725/article/details/137009386