剪绳子——jzoffer

如果面试题是求一个问题的最优解（通常是求最大值或者最小值），而且该问题能够分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决这个问题。

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

由于子问题在分解大问题的过程中重复出现，为了避免重复求解子问题，我们可以用从下往上的顺序先计算小问题的最优解并存储下来，再以此为基础求取大问题的最优解。

动态规划求解问题的特点总结：

1. 目标是求一个问题的最优解
2. 整体问题的最优解依赖于各个子问题的最优解
3. 我们把大问题分解成若干小问题，这些小问题之间还有相互重叠的更小的问题
4. 从上往下分析问题，从下往上求解问题

贪婪算法和动态规划不一样。当我们应用贪婪算法解决问题的时候，每一步都可以做出一个贪婪的选择，基于这个选择，我们确定能够得到最优解。

题目：给你一根长度为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)
  

  ​