钢条切割-动态规划（来自《算法导论》）

简介：
本文章介绍了一种利用动态规划解决钢条切割问题的方法，出自经典教材《算法导论》，旨在通过实例阐述动态规划的基本思想和应用技巧。 对于价格表样例的模拟切割如下：r1 = 1，切割方案为无切割；r2 = 5，同样选择不进行任何分割；r3 = 8，保持原状不做改动；r4 = 10，可以分成两个部分各占两单位或一个十单位的部分；对于数值 r5 则是被分成了三和二的组合。当遇到更大的数字如 r6（等于17）时，则无需切割直接使用整个数值作为方案。而面对更复杂的例子比如r7 = 18，可以考虑将它分为1与6或2、2和3这三个部分来处理；对于像r8这样的情况，可以选择将其分割为两个单位加上一个六单位的部分。 如果大家觉得这种切割方式有些复杂或者难以理解的话，那么采用动态规划的方法会更加有效。当使用模拟方法时，即使最终结果看起来很简单但整个过程却相当繁琐和耗时——例如，在处理7的数值时会有许多潜在组合如1-6,2-5,3-4以及更为复杂的像2-2-3或1-1-5等。然而，如果我们能够利用之前已经完成的小问题的答案来解决更大的问题，则可以大大简化过程。 具体来说，当切割一个较大数字（比如7）时，如果前面的数值都已经处理完毕的话，在此基础上进行切割只需要考虑几种可能的情况即可——例如对于r7中的1-6组合就涵盖了之前的多种情况如1-1-5或2-4等。通过这种方法可以大大减少需要手动模拟的过程数量和复杂度。