动态规划之切棍子问题
❝今天这道题和无限背包问题的思路是一模一样的。如果还没有看过无限背包问题强烈建议先看一下。
❞
对比思考，大家可以更深刻的体会，这两道题，外表形式看起来不同，但思维内核却完全一样。只有体会到思路上的共同性，掌握思维要领，才能做到举一反三。
问题描述
给定一根长度为n的棍子，我们要将其切割出售，以便获得最大收益。从1到n的不同长度的棍子的价格是已知的。
举例如下：
长度：[1、2、3、4、5]
价格：[2、6、7、10、13 ]
棍长：5
让我们尝试切割棍子：
五件长度1 => 10
两件长度2和一件长度1 => 14
一件长度3和两件长度1 => 11
一件长度3和一件长度2 => 13
一件长度4和一件长度1 => 12
一件长度5 => 13
这表明我们通过将棍子切成两个长度为2和一个长度为1的棍子出售，可以获得最高的价格14。
思路导引
在具体讲解这个题之前，我们先大概聊聊，绝大多数的算法题的基本思路。
首先，绝大多数算法题，从本质上讲，都是「求一个最优的组合」。这个最优有很多具体的形式：
-
最大价格（比如本题）
-
最长公共子串
-
最长窗口（比如滑动窗口问题）
-
最小子集
-
最短路径
-
等等
总之，这些题目的特征是非常的明显的，基本上一眼就能认出来。
对这些问题，有两个基本的解题思路：
-
穷举。遍历所有组合，寻找最优组合，一般会加入一些计算优化
-
分类。将所有组合分类，每类寻最优，各类最优比较得出答案
这两个思想是如此的简单，但是也是如此的深刻和通用。
「动态规划，滑动窗口，双指针，回溯等等都是具体的技巧，但是背后的思路都跳不出上面两个。」
穷举，这个大家都好理解。「难点在于如何做到穷举」。像回溯，递归这些技巧，都是可以帮助我们完成穷举的，关键是运用好这些技巧。
分类，这个思路所站的角度更高一些。使用这个思路时，很多文章都会介绍动态规划的状态转移方程。但是，根据我自己的经验，直接从寻找最优组合的角度进行思考会更自然和直接，这一点，在待会儿的具体解题中大家可以体会的。
当你面对一个问题没有思路时，不妨返璞归真，尝试从穷举和分类两个思路进行思考，也许就会柳暗花明又一村。
自上向下加记忆
「下面的解题过程中，大家可以放空大脑，假设完全没有学过动态规划，没有学过递归，就是一个算法萌新，看看我们是如何从分类这一个基本的思路出发，一点一点解决问题的。」
首先，我们定义，(n, 1)表示原问题，第一个n表示棍子的长度为n，第二个1表示可以将棍子切割成1-n的的长度，也就是一共有n个切割选项。假设最优的组合产生的价格为O(n,1)。S(n)表示长度为n的棍子的价格。
对于本题，我们可以这样思考，棍子有很多种切割的方法，每种方法其实就是一种切割组合。我们要找的是价格最高的那个组合。
那么多组合中，如何寻找最优的组合呢？
组合虽然有很多种，但是，我们可以将其分成两类：
-
组合中 「至少包含一个」长度为1的棍子
当组合中至少包含了一个长度为1的切割时，这类组合中最优的组合产生的价格就相当于 「S(1) + O(n-1, 1)」。n-1表示从原棍子中减去已经切割出来的长度为1的子棍。第二个1表示，仍然有1到n个可选切割。
-
组合中 「不包含」长度为1的棍子
这类组合中的最优组合，相当于子问题(n,2)的最优组合，即「O(n, 2)」。
然后我们只要从上面两个最优解中，选择更优的那个就可以了。
即：
「max(S(1) + O(n-1, 1), O(n, 2))」
我们可以递推一步，
「O(n, 2) = max(S(2)+O(n-2,2), O(n,3))」
本质还是对组合分类。
此时，我们的递推式，已经初具形状。下面，我们就要来考虑一下，边界条件。
边界条件一般分两类：
一种就是正确性条件，其实就是防止用户输入错误的数据。
另一种才是我们关注的真正的base问题条件。
「观察我们上面的递推式」，可以发现O(p,q) 在递推过程中， p在减小，q在增加。很自然的，就有了两个边界条件
p<= 0，棍子已经切割完了。
q > n，表示已经没有可用的切割选项了。
这两种情况下，结果都应该是0。
至此，我们已经将整个解决方案分析出来了，剩下的就是代码实现了。
代码实现
实现的时候，只要再加上一个缓存，就完美了。
代码如下所示：
def solve_rod_cutting(pirces, selects, rod_len):
dp = [[-1 for _ in range(rod_len+1)] for _ in range(len(pirces))]
return solve_rod_cutting_recursive(dp, pirces, selects, rod_len, 0)
def solve_rod_cutting_recursive(dp, prices, selects, rod_len, currentIndex):
n = len(prices)
if rod_len <= 0 or n == 0 or len(selects) != n or currentIndex >= n:
return 0
if dp[currentIndex][rod_len] == -1:
profit1 = 0
if selects[currentIndex] <= rod_len:
profit1 = prices[currentIndex] + solve_rod_cutting_recursive(
dp, prices, selects, rod_len - selects[currentIndex], currentIndex)
profit2 = solve_rod_cutting_recursive(
dp, prices, selects, rod_len, currentIndex + 1)
dp[currentIndex][rod_len] = max(profit1, profit2)
return dp[currentIndex][rod_len]
总结
以上的分析，我们尽可能从自然的思路出发去思考问题，逐步引出解决方案，思路衔接上非常自然。
很多讲动态规划的文章，上来就是最优子结构，好像这个子结构是某个牛叉的人发明的某种神奇的技术。其实，背后的思想就是简单的分类，我们高中数学中四大思想之一，那么问题来了，另外三个思想是什么呢？（手动狗头），加小编好友告诉我吧。