2020年7月30日 2020年7月30日 [整数拆分] integerBreak

2020年7月30日 整数拆分 integerBreak

class Solution {
    public int integerBreak(int n) {

    }
}

解题思路：

这道题必定有他动态规划来解决的一种算法，不过实际上不需要那么麻烦，我们只需稍微总结一下规律就能发现。

2=1*1=1

3=1*2=2

4=2*2=4

5=2*3=6

6=3*3=9

7=3*4=3*2*2=12

8=3*3*2=18

我们把一个数字拆分成若干个数字，要保证这个乘积最大，那么这个被拆分出的数字必定不能被继续拆分，因为如果可以继续拆分，那么拆分后的乘积必定大于当前乘积。

所以我们可以断定，任何一个大于等于4的数字，都是由若干个2和若干个3相乘得到的。

而且2不会超过2个，因为3个2组成的2*2*2是小于两个3组成的3*3的，所以我们只需要计算当前数和3的余数，根据余数的值来判断应该有几个2。

当余数为0时：

2的个数为0，例如6，9

6=3*3=9

9=3*3*3=27

当余数为1时，2的个数为2，例如7，10

7=3*2*2=12

10=3*3*3*2*2=36

当余数为2时，2的个数为1，例如5，8

5=2*3=6

8=2*3*3=18

代码实现：

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

    //求3的余数
    int num1=n%3;
    int num2=n/3;
    int res=1;
    for(int i=0;i<num2;i++){
        res*=3;
    }

    if (num1==2)
        return res*2;
    if (num1==1)
        return res*4/3;
    return res;


}