p94-p98 键指offer——动态规划与贪婪算法+面试题14：剪绳子

文章目录贪婪算法（贪心算法）面试题14：剪绳子
动态规划（dp，）
如果编程题是求一个问题的最优解（通常是最大值或最小值），而且该问题能够分解为若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决。
动态规划求解的问题的四大特点：求一个问题的最优解；整体问题的最优解是依赖各个子问题的最优解；大问题可以分成若干个子问题，这些子问题之间还有相互重叠的更小的子问题；从上往下分析问题，从下往上求解问题。
由于子问题在分解大问题的过程中重复出现，为了避免重复求解子问题，可以从下往上的顺序先计算出小问题的最优解并存储下来（一般都是存在一位数组或者二维数组里），并把子问题的最优解组合起来逐步解决大的问题。
动态规划功能强大，它能够解决子问题并使用这些答案来解决大问题。但仅当每个子问题都是离散的，即不依赖于其他子问题时，动态规划才管用。
理解过程：背包问题
假设你是个小偷，背着一个可装4磅东西的背包。
方法就是使用动态规划，先解决子问题，再逐步解决大问题。
最初网格是空的，当网格被你填满之后，就找到了问题的答案。
其实，在计算每个单元格的价值时，使用的公式都是相同的，不论是填充值的时候还是计算最大值的时候：

文章插图
练习：
方法就是之前的背包问题同样的解决方法：
总结：
? 需要在给定约束条件下优化某种指标时，动态规划很有用。
? 问题可分解为离散子问题时，可使用动态规划来解决。
? 每种动态规划解决方案都涉及网格。
? 单元格中的值通常就是你要优化的值。
? 每个单元格都是一个子问题，因此你需要考虑如何将问题分解为子问题。
? 没有放之四海皆准的计算动态规划解决方案的公式。
贪婪算法（贪心算法）
所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性（即某个状态以后的过程不会影响以前的状态，只与当前状态有关。）
所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。
该算法存在的问题：
不能保证求得的最后解是最佳的；
不能用来求最大值或最小值的问题；
只能求满足某些约束条件的可行解的范围。
贪婪算法适合用的问题：
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。
实际上，贪心算法适用的情况很少。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。
贪婪算法的优点——简单易行！贪婪算法很简单：每步都采取最优的做法。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。
在有些情况下，完美是优秀的敌人。有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。
面试题14：剪绳子
题目描述：
给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m≥1）。每段的绳子的长度记为k[0]、k[1]、……、k[m] 。k[0] * k[1] * … * k[m]可能的最大乘积是多少？例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18 。