动态规划问题——钢筋切割问题的两种解法解析@TOC

钢筋切割问题：

对于这个问题的两种解法

先来个官方点的解法说明：

我对两种解法的个人理解

第一种解法：
这种解法就是把先钢筋分成两部分，分别记为 i 和（n - i），这时候我们并不知道 i 和（n - i）各自的最优解是多少呀，那该怎么办？很简单，这时再把 i 和（n - i）看做成两条完全独立的钢筋，像一开始那样把它俩各自再次分成两部分…这样，到了最后，肯定会回归到1英寸钢筋的最优解是啥，这时候显而易见啦！（这种解法很容易理解，不懂的琢磨下，加油）

第二种解法：
这个解法我一开始是怎么也看不懂呀，后来想了几乎一个多小时才豁然开朗。话不多说，这就说下我的理解：
这个解法的意思就是，我把钢筋砍成两段，左边那段不管它（直接卖出去），右边那边做点小心思，求出最优解，再卖出去。我一开始的疑问就是：左边那段不求最优解？！那最后的结果是左右合并呀，左边都不是最优解，结果怎么可能是！后来仔细研究了一下别人的代码，才发现我太naive了！（贴上别人的代码哈）

（注意红色箭头这一行代码）
我觉得用一个实例来解释会更加明白：
我要切一条10英寸的钢筋了哈，
step 1：
我先把这条钢筋切成左边3英寸，右边7英寸（我假设，假设哈！这时候左3右7是最优的，即最终最优的切法是3+x+y+…+z=10，其中x+y+…+z=7。不接受任何反驳哈，因为是假设）。但是，虽然这时的切法是最优解，但我不知道右边的7寸的钢筋在最优的时候的切法是如何的呀。没关系，咱们再来对右边7寸的钢筋搞事情。
step 2：
我再把原来7寸的钢筋切成左边2英寸，右边5英寸，哈哈，这里又要假设啦（这时候左2右5是最优的，即最终最优的切法是2+x+y+…+z=7，其中x+y+…+z=5）。但是，这时候我们又遇见麻烦了，不知道右边5英寸的钢筋的最优切法是啥呀！没法子，再切呗。这样一直重复重复（对应于代码，就是红色箭头指出的递归）…
最后，这条10英寸的钢筋的最优切法就能得出来：3+2+？+？+？+…=10
对应于上面的代码，“ p[i-1]+cut(p, n-i) ”这段代码就是不断切割右边钢筋的过程。而代码里的for循环的作用就是用来找出每次把钢筋切成左右两部分时，怎么切才是最优的（对应于我上面假设的那部分，我step 1假设的是左3右7是最优的嘛，但实际情况可能不是哟，所以要每种分法（把钢筋分成左右两部分）都试一下，比如说：左1右9呀，左2右8呀，左7右3呀（注意左7右3和左3右7是不一样的呦）等等，所以要用到一个for循环）。