14. 剪绳子

来源

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

题目

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n 都是整数，n>1 并且 m>1），每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18。

示例:

示例 1.

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2.

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示：

• 2 <= n <= 58

思路 1

动态规划

n 小于 4 时，由于必须要切一刀，所以 F(2) = 1,F(3) = 2。结果反而没有不切大。
n 大于等于 4 时，2、3 就不需要再切 F(2) = 2，F(3) = 3。
设在 i 处切一刀，F(n) = F(i) × F(n-i)，得到公式：
F(n) = Max (F(2) × F(n-2) ... F(n/2) × F(n/2))。
用一个数组 cache 存储每个 n 对应的 F(n), 可以减少重复的计算。

解题

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function (n) {
  if (n === 2) return 1;
  if (n === 3) return 2;
  const cache = [0, 1, 2, 3];
  for (let i = 4; i <= n; i++) {
    let max = 0;
    for (let j = 2; j <= i / 2; j++) {
      let res = cache[j] * cache[i - j];
      if (max < res) max = res;
    }
    cache[i] = max;
  }
  return cache[n];
};

思路 2

贪婪算法

找规律

n	最优方案
2	1×1
3	1×2
4	2×2
5	2×3
6	3×3
7	3×4
8	3×3×2
9	3×3×3
10	3×3×4

除以 3 取余：
余 0，3 ^ n;
余 1，3 ^ (n-1) × 4;
余 2，3 ^ n × 2。

解题

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function (n) {
  if (n === 2) return 1;
  if (n === 3) return 2;
  const m = (n / 3) >> 0;
  if (n % 3 === 1) return 3 ** (m - 1) * 4;
  if (n % 3 === 2) return 3 ** m * 2;
  return 3 ** m;
};

题目 2

在原题目上加上条件，答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

解题

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function (n) {
  if (n === 2) return 1;
  if (n === 3) return 2;
  let m = (n / 3) >> 0;
  function pow3(n) {
    let x = 1;
    while (n > 0) {
      x = (x * 3) % 1000000007;
      n--;
    }
    return x;
  }
  if (n % 3 === 1) return (pow3(m - 1) * 4) % 1000000007;
  if (n % 3 === 2) return (pow3(m) * 2) % 1000000007;
  return pow3(m);
};

从零开始学算法
https://github.com/daqi/re0-algorithm/issues
欢迎 start & watch