剑指 Offer 14- I. 剪绳子

剑指 Offer 14- I. 剪绳子

• 解题思路
• 代码

解题思路

本题可以使用动态规划和贪心算法，但是由于贪心算法比动态规划要快！所以我们选择贪心算法。

其实这个题目有数学的规律，也即是把绳子切分成长度为3的小段，并且切分成的段越多，乘积就越大。但是n=2，n=3的时候就不用切分了，直接用这段剩下的长度去乘以之前求出来的乘积就可以了。
还要注意 输入的n就是小于4的。按道理不用切分即是最优长度，但是题目要求必须切分，所以就切成不规则的两端，返回n-1，这就是绳子的长度乘积。

代码

class Solution {
    public int cuttingRope(int n) {
        //base case：长度剩2或者3就不用切分了，这是最优的长度
        if(n<4){
            return n-1;
        }
        if(n==4){
            return 4;
        }

        int res=1;
        while(n>4){
            //把n切分成长度为3的n小段
            res=res*3;
            n=n-3;
        }

        //返回时还要乘以小于等于4的最后一小段（也就是不用再切分的那一段的长度）
        return res*n;
    }
}