java 代码

 public int integerBreak1(int n) {
        //1.动态规划
        //循环表示在J位置处切一刀，J之后的切最大为j*dp[i-j],不切最大为j*(i-j)
        int[]dp=new int[n+1];
        if(n==1||n==0)return 0;
        dp[0]=0;
        dp[1]=0;
        for (int i = 2; i <=n ; i++) {
            for (int j = 1; j < i; j++) {
                dp[i]=Math.max(dp[i],Math.max(j*dp[i-j],j*(i-j)));
            }
        }
        return dp[n];
    }
    public int integerBreak2(int n) {
        //2.贪心，尽可能切3，n>4时 3（n-3）>2(n-2)
        if(n==1||n==0)return 0;
        if(n==2)return 1;
        if(n==3)return 2;
        int ans=1;
        //取余3卫1能切出4则最大为4
        //取余3为2则能切出5 最大为6（或者最大为2切去2）
        //取余3为0则答案为3的n/3次方
        if(n%3==1){
            ans*=4;
            n-=4;
        }
        if(n%3==2){
            ans*=6;
            n-=5;
        }
        while (n>0){
            ans*=3;
            n-=3;
        }
        return ans;

    }