[数据结构与算法]【剑指 Offer】14- I. 剪绳子(详细解析)

第 32 日：I. 剪绳子

题目链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

题目

解题

1. 动态规划

   解题思路：
   动态规划还是比较容易理解的：
   1.创建dp数组，用来存放i（下标）的最大乘积
   2.初始化长度为2的最大乘积为1
   3.后面每次求最大乘积，根据自身和之前以求过的dp数组筛选最大值

   详细代码如下：

class Solution {
    public int cuttingRope(int n) {
        int[] dp=new int[n+1];
        dp[2]=1;
        for(int i=3;i<=n;i++){
            for(int j=2;j<i;j++){
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }
        return dp[n];
    }
}

2. 数学

   解题思路：

   由于1乘以任何数，都等于本身，所以我们选择从2开始分解
2:1+1、max=11=1
3:1+2、max=12=2
4:2+2、max=22=4
5:2+3、max=23=6
6:2+4、3+3、2+2+2、max=33=9
7:2+5、3+4、2+2+3、max=34=12
8:2+6、3+5、4+4、2+2+4、2+3+3、max=233=18
9:2+7、3+6、4+5、2+2+5、2+3+4、3+3+3、max=333=27
由上述，可知，从5开始，max总是等于以数字3为核心的各个数的乘积，我们得出结论，max的值，等于将n尽可能多的分解为数字3的乘积。

完整的数学推导可以看这里！

详细代码如下：

public int cuttingRope(int n) {
    if(n==2) return 1;
    if(n==3) return 2;
    if(n==4) return 4;

    int r=n%3,c=n/3;
    int res=0;
    
    if(r==1){
        res=4*(int)Math.pow(3,c-1);
    }else if(r==0){
        res=(int)Math.pow(3,c);
    }else{
        res=r*(int)Math.pow(3,c);
    }
    return res;
}