劍指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));  }

如此看來貪心算法能很快得到答案，但是需要紮實的數學功底。