题目链接

牛客网剑指offer - 剪绳子

算法思路

根据以前学过的数学知识可得，当一个数等分时，它的乘积之后是最大的。比如9，当9=3+3+3时，乘积之和333是最大的。

为什么举例3？而不是其他呢?
那是因为一个数最大分成3时，它的乘积才会最大。
当 n=1时，没什么好分的
当 n=2时，可以分成 2=1+1，但是它的乘积11=1，比2还小，还不如不分
当 n=3时，可以分成3=1+2，但是它的乘积12=2，比3还小，还不如不分

但是3之后的数字分段肯定比不分好。

有了上面的基础，就有以下两个思路

贪心算法

当n>4时，就每次贪心的选择最大，即以3来开始分
当n<4时，就不需要贪心了

动态规划

定义一个dp数组，dp[i]表示当绳子长为 i 时，最大乘积数
初始化dp数组。dp[2]=2,dp[3]=3。因为当n=2或者3时，不分是最好的
定义状态转移方程。dp[i] = Math(dp[i],dp[j] * dp[i-j])。一段绳子，它可以切分长度为j的绳子，另一半的绳子长度就为i-j。

代码实现

贪心实现

public class Solution {
    public int cutRope(int target) {
        if(target<4){
            return target-1;
        }
        int res = 1;
        while(target>4){
            target -= 3;
            res *= 3;
        }
        res *= target;
        return res;
    }
}

动规实现

public class Solution {
    public int cutRope(int target) {
        if(target<4){
            return target - 1;
        }
        //dp[i]表示长度为i时最大乘积
        int [] dp = new int[target+1];
        //初始化dp数组
        dp[2] = 2;
        dp[3] = 3;
        for(int i=4;i<=target;i++){
        	//为什么到i/2就行了？因为到i/2就是到绳子的一半了
        	//再往后切就和前面的重复了
            for(int j=1;j<=(i/2);j++){
                dp[i] = Math.max(dp[i],dp[j]*dp[i-j]);
            }
        }
        return dp[target];
    }
}