剑指offer_14_剪绳子

• 2019 年 10 月 6 日
• 筆記

动态规划：当绳子长度为n时，我们剪第一刀有n-1种可能，因为第一刀可以剪1米、2米、3米….n-1米。因此f(n) = max(f(i) * f(n – i))，其中0 < i < n。根据描述我们能写出如下代码：

public static int cut(int length) {      if(length < 2) {          return 0;      }      if(length == 2) {          return 1;      }      if(length == 3) {          return 2;      }      int[] storage = new int[length + 1];      // 初始化、这四个存的不是最优解而是用于计算的参数      storage[0] = 0;      storage[1] = 1;      storage[2] = 2;      storage[3] = 3;      // 定义一个变量来存储最大值      int max = 0;      // 从第四米开始storage存的是最优解      for (int i = 4; i <= length; i++) {          // 从小到大开始把每个子问题最优解存在数组里          for (int j = 1; j <= i / 2; j++) {              int multiply = storage[j] * storage[i - j];              if (multiply > max) {                  max = multiply;              }          }          storage[i] = max;      }      return storage[length];  }

贪心：如果我们按照下面这种策略来剪绳子，则得到的各段绳子的长度乘积最大：当n>=5时，我们尽可能的多剪长度为3的绳子，当剩下的绳子长度为4时，就把绳子剪成2段长为2的，比如长为7的绳子我们剪成3 * 2 * 2这样得到最大值为12。

public static int cut(int length) {      if(length < 2) {          return 0;      }      if(length == 2) {          return 1;      }      if(length == 3) {          return 2;      }      // 记录要剪成3m一段的段数      int three = length / 3;      // 余下1m说明要腾出来一段凑4m来剪两个2m      if (length - three * 3 == 1) {          // 腾出          three--;      }      // 要剪成2m的段数      int two = (length - three * 3) / 2;      return (int)(Math.pow(3,three) * Math.pow(2,two));  }

如此看来贪心算法能很快得到答案，但是需要扎实的数学功底。