如果面试题是求一个问题的最优解（通常是求最大值或者最小值），而且该问题能够分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决这个问题。
我们在应用动态规划之前要分析能否把大问题分解成小问题，分解后的每个小问题也存在最优解。如果把小问题的最优解组合起来能够得到整个问题的最优解，那么我们们可以应用动态规划。
由于子问题在分解大问题的过程中重复出现，为了避免重复求解子问题，我们可以用从下往上的顺序先计算小问题的最优解并存储下来，再以此为基础求取大问题的最优解。
动态规划求解问题的特点总结：
- 目标是求一个问题的最优解
- 整体问题的最优解依赖于各个子问题的最优解
- 我们把大问题分解成若干小问题，这些小问题之间还有相互重叠的更小的问题
- 从上往下分析问题，从下往上求解问题
贪婪算法和动态规划不一样。当我们应用贪婪算法解决问题的时候，每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。
题目：给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]*k[1]*....*k[m]可能的最大乘积是多少？
-
动态规划
class Solution: def max_product_afer_cut(self, length): # 如果特殊长度的绳子 if length < 2: return 0 if length == 2: return 1 if length == 3: return 2 products = [None] * (length + 1) # 如果绳子中有长度为1， 2， 3的段，不用去分剪它们 products[:4] = (0, 1, 2, 3) _max = 0 # 开始从下往上遍历求出每个小段的最大乘积 for i in range(4, length+1): _max = 0 for j in range(1, i//2 + 1): pro = products[j] * products[i-j] if _max < pro: _max = pro products[i] = _max _max = products[length] return _max -
贪婪算法
class Solution: def max_product_after_cut(self, length): # 特殊长度的绳子 if length < 2: return 0 if length == 2: return 1 if length == 3: return 2 times_of_three = length // 3 if (length - times_of_three * 3) == 1: times_of_three -= 1 times_of_two = length - times_of_three * 3 return pow(3, times_of_three) * pow(2, times_of_two)
