https://leetcode-cn.com/problems/integer-break/submissions/

Idea

非常的惭愧,这道题我本应该第一眼看到就知道怎么做的,因为显然,把数尽可能的化为e份即可使乘积最大
这是我高中学导数的第一题把 ……………… 没想到现在却完了.

Code

class Solution {
    public static int integerBreak(int n) {
        if(n==2) return 1;
        if(n==3) return 2;
        int count=0; //计算有多少个3
        while(n>4)
        {
            n-=3;
            count++;
        }
        return (int)(n*Math.pow(3,count));
    }
}

当然 数学解法是数学解法 做这道题的主要目的其实还是学习DP
dp算法
因为对于1个数n来说 他的最大值取决于 两个数相加 而其中一个数可以划分也可以不划分
据此我们可以写出状态转移方程

 public static int integerBreak(int n) {
        int[] memo=new int[n+1];
        memo[2]=1;
        for(int i=2;i<=n;i++)
            for(int j=1;j<i;j++)
            {
                if(memo[i]<Math.max(j*(i-j),j*memo[i-j]))
                    memo[i]=Math.max(j*(i-j),j*memo[i-j]);
            }
        return memo[n];
    }