1. 动态规划介绍 #
动态规划（Dynamic Programming，简称 DP）是一种算法设计方法，适用于解决具有重叠子问题和最优子结构性质的问题。 其基本思想是将复杂问题分解成更小的子问题，通过存储子问题的解来避免重复计算，从而提高效率。
- 动态规划的核心概念
- 重叠子问题：问题可以分解为相互重叠的子问题，即子问题会被多次计算。
- 最优子结构：问题的最优解可以由其子问题的最优解构造而来。
- 动态规划的步骤
- 定义状态：确定数组或矩阵的维度，定义状态
dp[i][j]表示问题在子问题 i, j 的最优解。 - 状态转移方程：找到状态之间的关系，写出状态转移方程，这一步是动态规划的核心。
- 初始状态和边界条件：确定初始状态和边界条件的值。
- 计算顺序：根据状态转移方程和初始状态，按照一定顺序计算各个状态的值。
- 返回结果：最后根据问题要求，返回所需状态的值。
- 定义状态：确定数组或矩阵的维度，定义状态
2. 斐波那契数列 #
- 斐波那契数列是递归的经典例子。其定义为：
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) （n ≥ 2）
- 以下是通过动态规划的方式实现：
def fibonacci(n): if n <= 1: return n dp = [0] * (n + 1) dp[1] = 1 for i in range(2, n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n] # 示例调用 print(fibonacci(10)) # 输出 55 - 也可以使用递归的方法实现，参考： 斐波那契数列-递归方法
2. 背包问题 #
2.1 0-1背包 #
给定一组物品，每个物品有重量和价值，在限定的总重量内，选择某些物品，使得总价值最大。这个问题称之为0-1背包问题。
2.1.1. 二维数组 #
- 解法一：二维 dp 数组
- 定义
dp[i][w]表示前 i 个物品中，总重量不超过 w 的最大价值。
- 定义
def knapsack(weights, values, capacity):
n = len(weights)
dp = [[0] * (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]
# 示例调用
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(knapsack(weights, values, capacity)) # 输出 7
i代表物品从1开始的索引，0 代表不放入物品。有 4 个物品的话，i的取值范围是1，2，3，4。w代表背包的剩余限重，0 代表背包没有剩余限重。for w in range(1, capacity + 1)这个遍历的作用是为了计算出所有剩余容量的情况下的最大价值，用w来表示当前剩余容量。
- 关于索引的说明：
dp[i - 1][w]代表的是不放入当前物品在包剩余容量为w时的总价值。- 由于 Python 的 index 是从 0 开始的，
weights[i - 1]和values[i - 1]分别代表第i个物品的重量和价值。 - 特别注意
dp的i-1指的是上一个物品的情况；而weights和values的i-1指的是当前物品。 - 因为
dp考虑到了不放物品和没有容量的情况；weights和values只是两个 Python 列表，记录物品的重量和价值。
if weights[i - 1] <= w：当前物品重量小于等于背包剩余限重。- 如果当前容量满足放下第 i 个物品，我们需要考虑是否放入该物品
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])- 不放入第 i 个物品
dp[i][w] =dp[i - 1][w]- 当前价值等于上个物品在剩余容量为 w 的价值
- 放入第 i 个物品
dp[i][w] = dp[i - 1][w - weights[i - 1]] + values[i - 1]- 当前价值等于上个物品在 w 减去当前物品重量时的价值加上当前物品的价值
- 对于这两种情况取最大值。
- 说明：当 w 不一样时，面对固定的 i 有可能是会有不一样的价值。容量会限定我们选择一些物品不放入，所以需要比较出最大值，来决定当前物品放还是不放。
- 不放入第 i 个物品
- 如果当前容量不满足放下第 i 个物品，使其等于上一个相同
w的情况：dp[i][w] = dp[i - 1][w]。
2.1.2. 一维数组 #
- 解法二：一维 dp 数组
def knapsack_1d(weights, values, capacity): n = len(weights) dp = [0] * (capacity + 1) for i in range(n): # 反向遍历背包容量，防止在同一轮迭代中重复使用物品 for w in range(capacity, weights[i] - 1, -1): dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) return dp[capacity] # 示例调用 weights = [2, 3, 4, 5] values = [3, 4, 5, 6] capacity = 5 print(knapsack_1d(weights, values, capacity))- 由解法一可以看出，当前物品放与不放，只和求上一个物品时得到的最优解有关。
- 更进一步来说，需要比较（当前容量下，不放当前物品）和（放了当前物品后，上一个物品在剩余容量下的最优解），然后取价值最高的，得到当前最优解。
- 使用一维数组的思想是，逐步用当前求出来的结果替换掉上一步求出来的结果。
- 有一个问题是，如果按照正序逐步替换，在计算放了当前物品后的最大价值，有可能左侧的值已经被替换掉了。
- 解决方法是，将 dp 倒序记录，也就是将剩余容量从大到小来考虑。
- 原因是 剩余容量 = 当前容量 - 当前物品的重量，所以剩余容量不可能会超过当前容量，也就不会跑到右边去。倒序后可以避免造成记录值的污染。
2.2. 完全背包 #
完全背包问题是背包问题的一种变体，其中每种物品可以选择多个（不限次数）放入背包，前提是总重量不超过背包的容量。 与0-1背包问题不同，这里每种物品可以放入背包多次。可以使用动态规划来解决完全背包的问题。
2.2.1. 二维数组 #
- 解法一：二维 dp 数组
def complete_knapsack_2d(weights, values, capacity):
n = len(weights)
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
if weights[i - 1] <= w:
dp[i][w] = max(dp[i - 1][w],
dp[i][w - weights[i - 1]]
+ values[i - 1])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][capacity]
# 示例调用
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(complete_knapsack_2d(weights, values, capacity))
- 在代码中，和0-1背包唯一的区别就在转换方程里的索引，其余都是一样的。
- 对于每个物品 i，我们有两种选择：不选择这个物品或选择这个物品多次。
- 同样，
dp[i-1][w]还是表示不选择第 i 个物品时，背包容量为 w 时的最大价值。 dp[i][w-weights[i-1]] + values[i-1]表示选择第 i 个物品且可以继续选择这个物品时，背包容量为 w 时的最大价值。dp[i][w-weights[i-1]]首先重量需要减去当前物品的重量，然后去寻找对应的i而不是i-1，因为物品可以重复放置。- 在
i和 限重等于w-weights[i-1]的时候已经求得了当前最优解，也就是考虑过i物品在此限重条件下是否放入背包，所以需要将索引从原先问题的i-1改成i。
- 同样，
2.2.2. 一维数组 #
- 解法二：一维 dp 数组
def complete_knapsack(weights, values, capacity):
n = len(weights)
# 创建一维数组 dp，其中 dp[j] 表示容量为 j 的背包所能容纳的最大价值
dp = [0] * (capacity + 1)
# 遍历每个物品
for i in range(n):
# 遍历每个可能的重量，从小到大，以确保物品可以被重复选择
for j in range(weights[i], capacity + 1):
dp[j] = max(dp[j], dp[j - weights[i]] + values[i])
return dp[capacity]
# 示例调用
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 5
print(complete_knapsack(weights, values, capacity))
- 和 0-1 背包问题的区别在于，我们这里需要考虑剩余重量从小到大正序计算。
- 在 0-1 背包问题中，我们要防止数据被污染；而这里我们需要用
i算出来的值来替代掉i-1计算出来的值。 - 原理与上面完全背包的二维数组解法类似。
3. 使用最小花费爬楼梯 #
- 题目描述：
- 给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
- 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
- 请你计算并返回达到楼梯顶部的最低花费。
- 示例 1：
- 输入：
cost = [10, 15, 20] - 输出：15
- 解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
- 总花费为 15 。
- 输入：
- 示例 2：
- 输入：
cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] - 输出：6
- 解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
- 总花费为 6 。
- 输入：
- 代码：
class Solution(object): def minCostClimbingStairs(self, cost): """ :type cost: List[int] :rtype: int """ n = len(cost) dp = [0] * (n+1) dp[0], dp[1] = cost[0], cost[1] for i in range(2, n+1): previous_cost = min(dp[i-1], dp[i-2]) if i == n: dp[i] = previous_cost else: dp[i] = previous_cost + cost[i] return dp[-1]- 由 dp 记录每一步最优解，长度为n+1，最后一个值代表抵达顶部的最优花费。
- i 定义为当前的台阶索引，0 和 1 分别代表第一步踏上第一个台阶和第一步踏上第二个台阶的费用。
- 遍历从2 开始，因为0和1的花费已知。
- 之前的最优花费就是比较
dp[i-1]和dp[i-2]的最小值，因为一次只能走一个台阶或者两个台阶。 - 当前最优总花费 = 之前最优花费 + 当前台阶的费用。
- 最后一步抵达顶部时没有花费，所以等于之前的最优总花费。
- 这个问题有不同的写法（参考 LeetCode 题解），但是这样的写法方便于本人自己的理解。