推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

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

输入描述

输入一个数n，意义见题面。（2 <= n <= 60）

public class Solution {
   
    public int cutRope(int target) {
   

    }
}

思路：

我们看一下规律：

 2 ： 1×1
 3 ： 1×2
 4 ： 2×2
 5 ： 2×3
 6 ： 3×3
 7 ： 2×2×3 或者4×3
 8 ： 2×3×3
 9 ： 3×3×3
10 ： 2×2×3×3 或者4×3×3
11 ： 2×3×3×3
12 ： 3×3×3×3
13 ： 2×2×3×3×3

可以看到，绳子长度大于3时，剪成段的长度时 2 或 3 （也可以是 2 或 3 的倍数，但是可以转换成 2 或 3 ，所以我们统一换成 2 或 3 。）;

并且还可以注意到，如果尽可能剪成长度为 3 的段之后，还剩余 1 ，那么应该少剪一个长度为 3 的段，把这一段留着，和剩余的 1 一起剪成两个长度为 2 的段，因为 2×2 > 1×3。

参考实现：

public class Solution {
   
    public int cutRope(int target) {
   
        //绳子小于3时的剪绳子
        if (target < 2) {
   
            return 0;
        }
        if (target == 2) {
   
            return 1;
        }
        if (target == 3) {
   
            return 2;
        }
        
        //绳子大于3时的剪绳子
        
        
        //先看一下最多能剪出长度为3的段
        int nums3 = target / 3;
        
        //如果全部剪成长度为3的段会剩余1，那么少剪一个长度为3的段，留着剪成长度为2的段
        //因为 3×1 < 2×2
        if (target - nums3 * 3 == 1) {
   
            nums3--;
        }
        
        //看看剩余绳子能剪成几个长度为2的段
        int nums2 = (target - nums3 * 3) / 2;
        
        //根据 3 和 2 的个数，返回最终的结果。
        return (int)(Math.pow(3, nums3)) * (int)(Math.pow(2, nums2));
        
    }
}

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！