of014-i.md

description
剑指 Offer 14- I. 剪绳子

OF14-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。

示例 ：

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

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

2 <= n <= 58

标签：

• 动态规划
• 数学

相似题目：

****343. 整数拆分****

题解

思路1 ： 动态规划

1. 对于的正整数 n，当 n≥2 时，可以拆分成至少两个正整数的和。令 k 是拆分出的第一个正整数，则剩下的部分是 n-k，n-k可以不继续拆分，或者继续拆分成至少两个正整数的和。由于每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积，因此可以使用动态规划求解。
2. 创建数组 dp，其中 dp[i] 表示将正整数 ii 拆分成至少两个正整数的和之后，这些正整数的最大乘积。特别地，0 不是正整数，1是最小的正整数，0和1都不能拆分，因此dp[0]=dp[1]=0。
3. 当 i≥2 时，假设对正整数 ii 拆分出的第一个正整数是j < i , 1≤j<i），则有以下两种方案：
   1. 将 ii 拆分成 j 和 i−j 的和，且 i-j不再拆分成多个正整数，此时的乘积是 j×(i−j)；
   2. 将 i拆分成 jj 和 i-j的和，且 i-j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]。
4. 因此，当 j 固定时，有 dp[i] - max(j*(i-j) j*dp[i-j])。由于 jj的取值范围是 1 到i−1，需要遍历所有的 j 得到 dp[i] 的最大值，因此可以得到状态转移方程如下：

$$ dp[i] = max( max (j \times (i-j) , j \times dp[i-j])) $$

1. 最终得到 dp[n] 的值即为将正整数 n 拆分成至少两个正整数的和之后，这些正整数的最大乘积。

复杂度分析：

• 时间复杂度$$O(1)$$：
• 空间复杂度$$O(1)$$：

代码

{% tabs %} {% tab title="Go" %}

func cuttingRope(n int) int {
    dp := make(map[int]int)
    dp[1] = 1 // 首项
    for i := 2; i < n+1; i++ {
        j, k := 1, i-1
        ans := 0
        for j <= k {
            ans = max(ans, max(j, dp[j])*max(k, dp[k])) // 递推公式
            j++
            k--
        }
        dp[i] = ans
    }
    return dp[n]
}

func max(x int, y int) int {
    if x > y {
        return x
    }
    return y
}

{% endtab %}

{% tab title="Python" %}

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(2, n + 1):
            for j in range(i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return dp[n]

{% endtab %}

{% tab title="Java" %}

class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        return dp[n];
    }
}

{% endtab %} {% endtabs %}

总结

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 算法 题解：awesome-golang-algorithm