求star

剪绳子I#

题目#

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是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

题解:key:#

①动态规划#

TIP

​ 因为每个正整数对应的最大乘积取决于比它小的正整数的最大乘积，所以可以使用动态规划求解。创建数组dp，dp[i]表示正整数i拆分成至少两个正整数之后，这些正整数的最大乘积。

​ 当i>=3时，假设对正整数i拆分出的第一个正整数是j，则接下来有两种选择：

• 将i拆分成 j 和 (i-j)后，不继续拆分，此时最大乘积为 j * (i-j)
• 将i拆分成 j 和 (i-j)后，继续拆分(i-j)，此时最大乘积为j * dp[i-j]

所以，当j固定时，dp[i] = Math.max(j * (i-j),j * dp[i-j])

时间复杂度: O(n^2)

空间复杂度: O(n)

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function (n) {
    if (n <= 3) return n - 1
    const dp = new Array(n).fill(0)
    for (let i = 3; i <= n; i++) {
        let curMax = 0
        for (let j = 1; j < i; j++) {
            curMax = Math.max(curMax, Math.max(j * (i - j),j * dp[i-j]))
        }
        dp[i] = curMax
    }
    return dp[n]
};

②优化的动态规划#

TIP

数论：

• 任何大于1的数都可由2和3相加组成（根据奇偶证明）
• 将数字拆成2和3，能得到的积最大

前面的动态规划，每次求dp[i]时，j都要遍历从1到i-1的所有值，所以总的时间复杂度是O(n^2)，有了以上结论，我们就可以只考虑j为2或3的情况了，可将时间复杂度降为O(n)

/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function (n) {
    if (n <= 3) return n - 1
    const dp = new Array(n).fill(0)
    dp[2] = 1
    for (let i = 3; i <= n; i++) {
        dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]))
    }
    return dp[n]
};