剑指 Offer 14- I. 剪绳子【DP循环】

难度等级：中等

上一篇算法：

变态跳台阶【递归循环】

力扣此题地址：

剑指 Offer 14- I. 剪绳子 - 力扣（Leetcode）

1.题目：剪绳子

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

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

2.解题思路：

数论

1. 任何大于1的数都可由2和3相加组成（根据奇偶证明）
2. 因为2*2=1*4，2*3>1*5, 所以将数字拆成2和3，能得到的积最大
3. 因为2*2*2<3*3, 所以3越多积越大 时间复杂度O(n/3)，用幂函数可以达到O(log(n/3)), 因为n不大，所以提升意义不大，我就没用。 空间复杂度常数复杂度O(1)

3.代码实现：

class Solution {
    public int cuttingRope(int n) {
        if (n<=3) return n-1;//小于等于3的结果遵循n - 1
        int div = n/3; //得到3的个数
        int rem = n % 3;//得到n模3的余数，看是否是2
        long result = 1;
        for (int i = 0; i < div; i++) {
            result *= i1 ? 3 : (rem == 2 ? 3*rem : (3+rem));
            if (result >= 1000000007) {
                result = result % 1000000007;
            }
        }
        return (int)result;
    }
}

4.写在最后：

这题这样解是双百解法，简单的数论题，DP并不是最优解，套用DP谁都会，而数论会让面试官眼前一亮(尤其如果面试官水平一般的话，只认为DP才能解，数论时间复杂度空间复杂度都远胜DP，他就会怀疑正确性，你即使告诉他怎么证明的，他也会拉着你的代码逐行带入计算，最后被震惊的话，恭喜你幸运的拿到一个SH)。

数论定义：

数学的一个分科，主要研究正整数的性质及其有关的规律。按研究方法的不同，大致可分为初等数论、代数数论、几何数论、解析数论等。