【算法进阶2-动态规划】斐波那契数列(递归调用、动态规划)、钢条切割问题(自定而下实现、自底向上、切割方案)

1 斐波那契数
2 钢条切割问题
2.1 最优解情况
2.2 钢条切割问题之自定而下实现
2.3 钢条切割问题之自底向上实现
2.4 钢条切割问题-重构解-切割方案

1 斐波那契数

# 1 子问题的重复计算
def fibonacci(n: int) -> int:"""使用递归方式计算第 n 个斐波那契数。该方法效率低，因为会重复计算相同的子问题。:param n: 要计算的斐波那契数的索引（从 1 开始）:return: 返回第 n 个斐波那契数"""# 基础情况：第 1 个和第 2 个斐波那契数都是 1if n == 1 or n == 2:return 1else:# 递归调用：第 n 个斐波那契数等于前两个斐波那契数之和return fibonacci(n - 1) + fibonacci(n - 2)print(fibonacci(10))  # 使用递归方法，输出 55# 2 动态规划--》递推式
def fibonacci_no_recursion(n: int) -> int:"""使用迭代方式计算第 n 个斐波那契数，避免递归的重复计算。:param n: 要计算的斐波那契数的索引（从 1 开始）:return: 返回第 n 个斐波那契数"""# 初始化斐波那契数列的前两个值f = [0, 1, 1]# 当 n 大于 2 时，通过迭代计算后续的斐波那契数if n > 2:for i in range(n - 2):# 计算下一个斐波那契数，并将其添加到列表中num = f[-1] + f[-2]f.append(num)# 返回第 n 个斐波那契数return f[n]print(fibonacci_no_recursion(100))  # 354224848179261915075

2 钢条切割问题

在这里插入图片描述

2.1 最优解情况

在这里插入图片描述

2.2 钢条切割问题之自定而下实现

import timedef cal_time(func):"""装饰器，用于计算函数的执行时间。:param func: 被装饰的函数:return: 包装后的函数，附加了执行时间的计算"""def wrapper(*args, **kwargs):# 记录开始时间t1 = time.time()# 执行被装饰的函数并获取返回值result = func(*args, **kwargs)# 记录结束时间t2 = time.time()# 计算并打印函数运行时间print(f"{func.__name__} running time: {t2 - t1} seconds.")# 返回函数执行的结果return resultreturn wrapperdef cut_rod_recurision_1(p: list, n: int) -> int:"""使用递归方法求解钢条切割问题。钢条切割问题的目标是将一根长度为 n 的钢条切成若干段，使得每段的总价值最大化。价格由列表 p 提供，其中 p[i] 表示长度为 i 的钢条的价格。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回长度为 n 的钢条的最大收益"""# 如果钢条长度为 0，则最大收益为 0if n == 0:return 0# 初始化最大收益为切割长度为 n 的收益res = p[n]# 递归地计算所有可能的切割方式for i in range(1, n):# 对每个可能的切割点 i，计算最大收益res = max(res, cut_rod_recurision_1(p, i) + cut_rod_recurision_1(p, n - i))return res# price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
# print(cut_rod_recurision_1(price, 9))  # 25def cut_rod_recurision_2(p: list, n: int) -> int:"""使用递归方法求解钢条切割问题的优化版本。该函数通过递归计算长度为 n 的钢条的最大收益。钢条的价格由列表 p 提供，其中 p[i] 表示长度为 i 的钢条的价格。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回长度为 n 的钢条的最大收益"""# 如果钢条长度为 0，则最大收益为 0if n == 0:return 0# 初始化最大收益为 0，因为我们可能不切割钢条，即收益为 0res = 0# 递归地计算所有可能的切割方式for i in range(1, n + 1):# 对每个可能的切割点 i，计算当前切割方案的收益# res = max(当前最大收益, 将钢条切成长度 i 和 n-i 两部分的收益)res = max(res, p[i] + cut_rod_recurision_2(p, n - i))# 返回最大收益return res# price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
# print(cut_rod_recurision_2(price, 9))  # 25price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 28, 30, 33, 36, 37, 39, 40]
# print(len(price))
# print(cut_rod_recurision_2(price, 20))  # 56@cal_time
def c1(p: list, n: int) -> int:"""使用装饰器 cal_time 来计算并打印 cut_rod_recurision_1 函数的运行时间。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回长度为 n 的钢条的最大收益"""return cut_rod_recurision_1(p, n)@cal_time
def c2(p: list, n: int) -> int:"""使用装饰器 cal_time 来计算并打印 cut_rod_recurision_2 函数的运行时间。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回长度为 n 的钢条的最大收益"""return cut_rod_recurision_2(p, n)print(c1(price, 20))
print(c2(price, 20))

2.3 钢条切割问题之自底向上实现

在这里插入图片描述

import timedef cal_time(func):"""装饰器，用于计算函数的执行时间。:param func: 被装饰的函数:return: 包装后的函数，附加了执行时间的计算"""def wrapper(*args, **kwargs):# 记录开始时间t1 = time.time()# 执行被装饰的函数并获取返回值result = func(*args, **kwargs)# 记录结束时间t2 = time.time()# 计算并打印函数运行时间print(f"{func.__name__} running time: {t2 - t1} seconds.")# 返回函数执行的结果return resultreturn wrapperdef cut_rod_recurision_2(p: list, n: int) -> int:"""使用递归方法求解钢条切割问题的优化版本。该函数通过递归计算长度为 n 的钢条的最大收益。钢条的价格由列表 p 提供，其中 p[i] 表示长度为 i 的钢条的价格。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回长度为 n 的钢条的最大收益"""# 如果钢条长度为 0，则最大收益为 0if n == 0:return 0# 初始化最大收益为 0，因为我们可能不切割钢条，即收益为 0res = 0# 递归地计算所有可能的切割方式for i in range(1, n + 1):# 对每个可能的切割点 i，计算当前切割方案的收益# res = max(当前最大收益, 将钢条切成长度 i 和 n-i 两部分的收益)res = max(res, p[i] + cut_rod_recurision_2(p, n - i))# 返回最大收益return resprice = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 28, 30, 33, 36, 37, 39, 40]@cal_time
def c2(p: list, n: int) -> int:"""使用装饰器 cal_time 来计算并打印 cut_rod_recurision_2 函数的运行时间。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回长度为 n 的钢条的最大收益"""return cut_rod_recurision_2(p, n)@cal_time
def cut_rod_dp(p: list, n: int) -> int:"""钢条切割问题的动态规划解决方案，自底向上实现。该函数通过动态规划方法求解长度为 n 的钢条的最大收益。钢条的价格由列表 p 提供，其中 p[i] 表示长度为 i 的钢条的价格。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回长度为 n 的钢条的最大收益"""# 初始化一个长度为 n+1 的列表 r，其中 r[i] 表示长度为 i 的钢条的最大收益r = [0] * (n + 1)# 遍历每一个可能的钢条长度 ifor i in range(1, n + 1):# 对于每个长度 i，初始化当前最大收益为 0res = 0# 遍历所有可能的切割点 j，从 1 到 ifor j in range(1, i + 1):# 计算切割方案的收益，并更新最大收益# res = max(当前最大收益, 切割成长度 j 和 i-j 两部分的收益)res = max(res, p[j] + r[i - j])# 将长度为 i 的钢条的最大收益存储在 r[i]r[i] = res# 返回长度为 n 的钢条的最大收益return r[n]print(cut_rod_dp(price, 15))  # 42

2.4 钢条切割问题-重构解-切割方案

在这里插入图片描述

import time
from typing import Tuple, Listdef cal_time(func):"""装饰器，用于计算函数的执行时间。:param func: 被装饰的函数:return: 包装后的函数，附加了执行时间的计算"""def wrapper(*args, **kwargs):# 记录开始时间t1 = time.time()# 执行被装饰的函数并获取返回值result = func(*args, **kwargs)# 记录结束时间t2 = time.time()# 计算并打印函数运行时间print(f"{func.__name__} running time: {t2 - t1} seconds.")# 返回函数执行的结果return resultreturn wrapperdef cut_rod_recurision_2(p: list, n: int) -> int:"""使用递归方法求解钢条切割问题的优化版本。该函数通过递归计算长度为 n 的钢条的最大收益。钢条的价格由列表 p 提供，其中 p[i] 表示长度为 i 的钢条的价格。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回长度为 n 的钢条的最大收益"""# 如果钢条长度为 0，则最大收益为 0if n == 0:return 0# 初始化最大收益为 0，因为我们可能不切割钢条，即收益为 0res = 0# 递归地计算所有可能的切割方式for i in range(1, n + 1):# 对每个可能的切割点 i，计算当前切割方案的收益# res = max(当前最大收益, 将钢条切成长度 i 和 n-i 两部分的收益)res = max(res, p[i] + cut_rod_recurision_2(p, n - i))# 返回最大收益return res# price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 28, 30, 33, 36, 37, 39, 40]@cal_time
def c2(p: list, n: int) -> int:"""使用装饰器 cal_time 来计算并打印 cut_rod_recurision_2 函数的运行时间。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回长度为 n 的钢条的最大收益"""return cut_rod_recurision_2(p, n)@cal_time
def cut_rod_dp(p: list, n: int) -> int:"""钢条切割问题的动态规划解决方案，自底向上实现。该函数通过动态规划方法求解长度为 n 的钢条的最大收益。钢条的价格由列表 p 提供，其中 p[i] 表示长度为 i 的钢条的价格。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回长度为 n 的钢条的最大收益"""# 初始化一个长度为 n+1 的列表 r，其中 r[i] 表示长度为 i 的钢条的最大收益r = [0]  # 只包含一个元素 0，后续会扩展到长度为 n+1# 遍历每一个可能的钢条长度 i 从 1 到 nfor i in range(1, n + 1):# 对于每个长度 i，初始化当前最大收益为 0res = 0# 遍历所有可能的切割点 j，从 1 到 ifor j in range(1, i + 1):# 计算当前切割方案的收益，并更新最大收益# 比较当前最大收益和切割成长度 j 和 i-j 两部分的收益res = max(res, p[j] + r[i - j])# 将长度为 i 的钢条的最大收益存储在 r[i]r.append(res)# 返回长度为 n 的钢条的最大收益return r[n]# price = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 28, 30, 33, 36, 37, 39, 40]
# print(cut_rod_dp(price, 20))  # 56from typing import List, Tupledef cut_rod_extend(p: list, n: int) -> Tuple[int, List[int]]:"""扩展的钢条切割问题动态规划解决方案，自底向上实现。该函数不仅计算长度为 n 的钢条的最大收益，还追踪实现最大收益的切割方案。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回一个元组，其中第一个元素是长度为 n 的钢条的最大收益，第二个元素是一个列表，表示每个长度的钢条的最佳切割点"""# 初始化一个长度为 n+1 的列表 r，其中 r[i] 表示长度为 i 的钢条的最大收益r = [0] * (n + 1)# 初始化一个长度为 n+1 的列表 s，用于存储每个长度的钢条的最佳切割点s = [0] * (n + 1)# 遍历每一个可能的钢条长度 ifor i in range(1, n + 1):# 对于每个长度 i，初始化当前最大收益为 0res_r = 0  # 当前长度 i 的最大收益res_s = 0  # 对应最大收益的最佳切割长度# 遍历所有可能的切割点 j，从 1 到 ifor j in range(1, i + 1):# 比较通过切割长度 j 和 i-j 两部分的收益是否大于当前最大收益if p[j] + r[i - j] > res_r:# 更新最大收益和最佳切割长度res_r = p[j] + r[i - j]res_s = j# 将当前长度 i 的最大收益和最佳切割长度存储在 r 和 s 列表中r[i] = res_rs[i] = res_s# 返回长度为 n 的钢条的最大收益和最佳切割点列表return r[n], sdef cut_rod_solution(p: list, n: int) -> list:"""根据最佳切割点列表还原钢条切割方案该函数使用最佳切割点列表 `s` 还原出钢条的切割方案。:param p: 列表，包含各个长度的钢条对应的价格，p[0] 通常为 0:param n: 钢条的总长度:return: 返回一个列表，表示钢条的切割方案"""# 调用 cut_rod_extend 函数获取最佳切割点列表_, s = cut_rod_extend(p, n)ans = []  # 存储最终的切割方案while n > 0:# 将当前长度的最佳切割点添加到切割方案中ans.append(s[n])# 更新剩余长度n -= s[n]# 返回最终的切割方案return ansprice = [0, 1, 5, 8, 9, 10, 17, 17, 20, 21, 23, 24, 26, 27, 28, 30, 33, 36, 37, 39, 40]
_, s = cut_rod_extend(price, 20)
print(s)  # [0, 1, 2, 3, 2, 2, 6, 1, 2, 3, 2, 2, 6, 1, 2, 3, 2, 2, 6, 1, 2]
print(cut_rod_extend(price, 20))  # (56, [0, 1, 2, 3, 2, 2, 6, 1, 2, 3, 2, 2, 6, 1, 2, 3, 2, 2, 6, 1, 2])
print(cut_rod_solution(price, 20))  # [2, 6, 6, 6]