前言

动态规划也是编程面试中的常考题。如果所求问题是求最优解，而且问题能够分解为若干个子问题，并且子问题之间还有重叠的更小的子问题，那么应该考虑应用动态规划思想求解。

在应用动态规划之前要分析能否把大问题分解成小问题，分解的每个小问题也存在最优解。如果把小问题的最优解组合起来能够得到这个问题的最优解，那么我们就可以应用动态规划解决这个问题。

总之，动态规划存在以下几个特点：

目标问题是求最优解；
整体的最优解可以由子问题的最优解参与或组合得到；
大问题可以分成若干个子问题，且子问题之间还有相互重叠的更小的子问题；
为避免重复求解子问题(后面求大问题的时候可能多次用到)，采用自下而上的顺序先计算小问题的最优解并记录到一维或二维数组中，再根据已经解出的小问题来求出大问题的最优解。简而言之，就是自上而下分析问题，自下而上求解问题。

题目(剪绳子)

题目：给定一根长度为n的绳子，请把绳子剪成 m 段(m,n 都是整数且均大于 1，至少剪一刀)，每段绳子的长度记为 k[0],k[1],…,k[m]。请问 k[0]xk[k1]x…xk[m] 可能的最大乘积是多少？例如，绳子长度为 8，可分成 2，3，3，三段，最大乘积为 18。

解题思路

动态规划法

首先定义函数 f(n) 为把长度为 n 的绳子剪成若干段后的最大乘积值。
剪绳子求的是最大乘积值满足特点 1；如果在绳子的 i 处剪一刀，那么 f(n) 要达到乘积最大，则 f(i)与 f(n-i) 也要达到乘积最大，满足特点 2；假设 n=6，那么 f(2) 和 f(4) 都是问题的子问题，但其实 f(2) 也是 f(4) 的子问题，那么就出现了重叠的更小的子问题，满足特点 3；所以，我们为了求解目标问题，都是先从小问题开始求解，即自下而上求解，并将每个子问题的乘积最大值记录到数组中备查，满足特点4。因此，本题的确适合采用动态规划求解。

当绳子长度为 2 的时候，只能剪成两段长度为 1，所以 f(2)=1；当绳子长度为 3 的时候，有两种剪法，其中最大的 f(3)=2。

那么当 n>4 的时候，我们要求出把长度为 i 的绳子剪成若干段之后各段长度乘积的最大值，即求 f(i)，而4<=i<=n，即要求出所有子问题的最优解。那么对于每个子问题 f(i)，由于可以有 i/2 种切法，所以我们应该遍历每种切法，并计算出乘积最大的那种切法。当切点在 j(1<=j<=i/2) 处时，子问题 f(i)=max(f(j)xf(i-j)),其中 f(j),f(i-j)，都可以从备忘数组中查询得到。

贪心算法

即选择一个能够得到乘积最大值的策略进行。当 n>=5 时，我们尽可能的剪出长度为 3 的小绳子；当剩下的绳子长度为 4 时，改为把绳子剪成两段。
证明 :首先，当 n>=5 时，我们可以证明 2(n-2)>n 并且 3(n-3)>n。也就是说，当绳子剩下的长度大于或者等于 5 的时候，我们就把它剪成长度为 3 或者 2 的绳子段。另外，当 n>=5 时，3(n-3)>=2(n-2)，因此我们应该尽可能地多剪长度为3的绳子段。而当 n=4 时，由于 2x2>1x3 所以应该剪成两条长度分别为 2 的绳子段。

算法实现

动态规划实现

贪心算法实现

复杂度分析

对于动态规划法，两层循环，时间复杂度为 O(n^2)，另外，建立了辅助容器，空间复杂度为 O(n)；对于贪心算法，复杂度均为 O(1)。

参考

<<剑指offer2>>