剑指 Offer 14- I. 剪绳子-Toy模板网

这篇具有很好参考价值的文章主要介绍了剑指 Offer 14- I. 剪绳子。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

剑指 Offer 14- I. 剪绳子

难度： $\color{orange}{middle}$

题目描述

给你一根长度为 $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

提示：

$2 <= n <= 58$

注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/

算法一

(数学推导 + 贪心)

设将长度为 n 的绳子切为 a 段：

$n = n_1 + n_2 + n_3 + n_4+...+n_a$

本题等价于求解：

$max( n_1 * n_2 * n_3 * n_4 *... *n_a)$

推论一：将绳子以相等的长度等分为多段，得到的乘积最大。

推论二：尽可能将绳子以长度 3 等分为多段时，乘积最大。

切分规则：

最优： 3 。把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,2 三种情况。
次优： 2 。若最后一段绳子长度为 2 ；则保留，不再拆为 1+1 。
最差： 1 。若最后一段绳子长度为 1 ；则应把一份 3+1 替换为 2+2，因为 2×2>3×1。

剑指 Offer 14- I. 剪绳子

复杂度分析

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

C++ 代码

class Solution {
public:
    int cuttingRope(int n) {
        if (n <= 3) return n - 1;
        int a = n / 3;
        int b = n % 3;
        
        if (b == 0) return pow(3, a);
        if (b == 1) return pow(3, a - 1) * 4;
        return pow(3, a) * 2;
    }
};

算法二

(动态规划)

创建数组 dp，其中 dp[i] 表示将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积。特别地，0 不是正整数，1 是最小的正整数，0 和 1 都不能拆分，因此 dp[0]=dp[1]=0。

当 i≥2 时，假设对正整数 i 拆分出的第一个正整数是 j（1≤j<i），则有以下两种方案：

将 i 拆分成 j 和 i−j 的和，且 i−j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；

将 i 拆分成 i−j 的和，且 i−j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]。

因此，当 j 固定时，有 dp[i]=max(j×(i−j), j×dp[i−j])。由于 j 的取值范围是 1 到 i−1，需要遍历所有的 j 得到 dp[i] 的最大值，因此可以得到状态转移方程如下：

$dp[i]= max_{1≤j<i}( { max(j×(i−j),j×dp[i−j])})$

最终得到 dp[n] 的值即为将正整数 n 拆分成至少两个正整数的和之后，这些正整数的最大乘积。文章来源地址https://www.toymoban.com/news/detail-409006.html

复杂度分析

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

C++ 代码

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> f(n + 1);

        for (int i = 2; i <= n; i ++)
        {
            int maxnun = 0;;
            for (int j = 1; j < i ; j ++)
            {
                maxnun = max(maxnun, max(j * (i - j), j * f[i - j]));
            }
            f[i] = maxnun;
        }

        return f[n];
    }
};