本文共 1662 字，大约阅读时间需要 5 分钟。

问题描述如下：

给定一段长度为 n 的钢条和一个价格表 pi （i = 1, 2, ..., n ），求切割钢条的方案，是的销售收益 r 最大。

朴素递归：

/*	朴素递归算法，计算当钢条长度为 n 时，计算最大收益	输入参数：		p：价格数组，长度为 i 的钢条的价格为 p[i]		n：钢条长度	返回值：		最大收益*/CUT-ROD( p, n )	if n == 0			// 递归结束的条件：钢条的长度为 0		return 0	q = -1				// 初始化价格为 0	for i = 1 to n		// 计算钢条长度从 1 到 n 时的最大收益		q = max( q, p[i] + CUT-ROD( p, n - i ) )	// 递归计算	return q

采用朴素递归算法形成的递归调用树会重复求解子问题，导致效率低下

朴素递归的递归调用树：

带备忘的自顶向下算法：

/*	自顶向下算法，计算当钢条长度为 n 时，计算最大收益	输入参数：		p：价格数组，长度为 i 的钢条的价格为 p[i]		n：钢条长度	返回值：		最大收益*/MEMOIZED-CUT-ROD( p, n )	let r[0, ..., n] be a new array				// 用一个数组 r 来记录递归沿途的结果	for i = 0 to n 								// 初始化数组的每个元素为 -1 		r[i] = -1	return MEMOIZED-CUT-ROD-AUX( p, n, r ) 		// 调用辅助函数/*	自顶向下算法的辅助函数，实现了递归计算最大收益	输入参数：		p：价格数组，长度为 i 的钢条的价格为 p[i]		n：钢条长度		r：备忘录数组，保存着计算了的收益	返回值：		最大收益*/ MEMOIZED-CUT-ROD-AUX( p, n, r ) 	if r[n] >= 0 								// 如果数组元素值大于 0，说明已经计算过其值（备忘机制） 		return r[n] 							// 不进入递归，直接返回结果 	if n == 0									// 如果钢条的长度为 0 		q = 0									// 最大收益为 0 	else q = -1 				 		for i = 1 to n 							 			q = max( q, p[i] + MEMOIZED-CUT-ROD-AUX( p, n, r ) ) // 计算从 1 到 n 时的最大收益 	r[n] = q 									// 计算结果放入备忘录数组 	return q

  相对于朴素递归算法，自顶向下算法不必重复计算子问题，减小了函数调用规模，简化了递归调用树

 自底向上的算法

/*	自底向上算法，计算当钢条长度为 n 时，计算最大收益	输入参数：		p：价格数组，长度为 i 的钢条的价格为 p[i]		n：钢条长度	返回值：		最大收益数组*/ BOTTOM-UP-CUT-ROD( p, n ) 						 	let r[0, ..., n] be a new array 			// 保存子问题的数组 	r[0] = 0									// 令最小的子问题：当钢条长度为 0 时最大收益为 0 	for j = 1 to n 								// 计算钢条长度从 1 到 n 时的最大收益 		q = -1 									// 初始为最大收益为 -1 		for i = 1 to j 							 			q = max( q, p[i] + r[i - j] ) 		// 计算子问题的最大收益 		r[i] = q 								// 结果放入子问题数组 	return r[n] 								// 最大收益数组

 自顶向下算法和自底向上算法的时间复杂度均为 O(n ^ 2)，但是自底向上算法采用的迭代计算，相对于自顶向下的递归计算，空间复杂度更低