代码随想录算法训练营第三十一天丨15.1钢条切割、LCR 126. 斐波那契数/习题15.1-5、53. 最大子数组和

本文主要是介绍代码随想录算法训练营第三十一天丨15.1钢条切割、LCR 126. 斐波那契数/习题15.1-5、53. 最大子数组和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 15.1钢条切割

假设你有一根长度为n英寸的钢条和一个价格表，表中列出了不同长度的钢条的售价。你可以选择不同的方式切割这根钢条，然后将切割后的各段钢条按照价格表出售。目标是确定如何切割钢条以使得销售收益最大化。

问题的输入是一个价格表P[i]，其中i=1,2,...,n，表示长度为i英寸的钢条的价格，以及钢条的总长度n。问题的输出是最大收益R[n]以及达到这个最大收益时各段钢条的长度。

解决这个问题的动态规划方法涉及将问题分解为更小的子问题，然后逐步构建解决原问题的方法。具体来说，动态规划算法会计算出对于每个长度i（1 <= i <= n），切割钢条所能得到的最大收益R[i]。这是通过比较不切割钢条（即直接出售整根钢条）和所有可能的切割方案（即将钢条切割为两部分，并递归地计算这两部分的最大收益）的收益来实现的。

算法的关键是避免重复计算相同子问题的解，这通常通过两种方式实现：

1. 自顶向下的备忘录方法：这种方法首先尝试解决最大规模的问题，即求R[n]，并在递归过程中，将所有小于n的R[i]的值存储在一个数组中，以避免重复计算。
2. 自底向上的方法：这种方法从最小的子问题开始，即R[1]，然后逐步计算所有R[i]直到R[n]。这种方法利用了子问题的解依赖于更小的子问题的解这一事实，通过迭代计算而不是递归来避免重复计算。

自顶向下的递归方法：

def cut_rod(p, n):if n == 0:return 0q = -float('inf')for i in range(1, n + 1):q = max(q, p[i] + cut_rod(p, n - i))return q

带备忘的自顶向下方法：

def memoized_cut_rod(p, n):# 初始化备忘录，所有值设为 None 表示未计算r = [None] * (n + 1)def cut_rod_aux(n):"""辅助递归函数，使用备忘录避免重复计算。:param n: 当前考虑的钢条长度。:return: 长度为 n 的钢条的最大收益。"""if r[n] is not None:return r[n]if n == 0:q = 0else:q = -float('inf')for i in range(1, n + 1):q = max(q, p[i] + cut_rod_aux(n - i))r[n] = qreturn qreturn cut_rod_aux(n)

自底向上的方法：

def bottom_up_cut_rod(p, n):# 初始化收益数组r，r[i] 存储长度为 i 的钢条的最大收益r = [0] * (n + 1)# 从最小子问题开始，逐步计算所有长度的最大收益for j in range(1, n + 1):q = -float('inf')# 对于每个长度j，尝试所有可能的第一段切割长度ifor i in range(1, j + 1):q = max(q, p[i] + r[j - i])r[j] = qreturn r[n]

LCR 126. 斐波那契数/习题15.1-5

入门级别的动态规划题目。

类似钢条切割，使用dp数组：

class Solution:def fib(self, n: int) -> int:if n == 0: return 0r = [0] * (n + 1)r[1] = 1for i in range(2, n + 1):r[i] = r[i - 1] + r[i - 2]return r[n] % 1000000007

空间复杂度是O(1)解法：

def fib(n):"""计算斐波那契数列的第n个数，使用动态规划（自底向上）。:param n: 斐波那契数列的索引:return: 第n个斐波那契数"""if n <= 1:return n# 初始化存储前两个斐波那契数的变量prev, curr = 0, 1for i in range(2, n + 1):prev, curr = curr, prev + currreturn curr

53. 最大子数组和

class Solution:def maxSubArray(self, nums: List[int]) -> int:current_max, global_max = nums[0], nums[0]for num in nums[1:]:current_max = max(num, current_max + num)global_max = max(current_max, global_max)return global_max

好像懂了，又好像没懂，以后系统刷到动态规划再说。

这篇关于代码随想录算法训练营第三十一天丨15.1钢条切割、LCR 126. 斐波那契数/习题15.1-5、53. 最大子数组和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---