leetcode 剑指 Offer 14- I. 剪绳子

0.code

class Solution {
    public int cuttingRope(int n) {
        int max = 0;
        for(int i=1;i<=n-1;i++){
            int ans = cuttingRopeHelp(i,n);
            max = max>ans?max:ans;
        }
        return max;
    }
    public int cuttingRopeHelp(int i,int n){
        int avg = n/(i+1);
        int res = n%(i+1);
        int re = 1;
        for(int j=1;j<=res;j++){
            re = re*(avg+1);
        }
        for(int j=res+1;j<=(i+1);j++){
            re = re*avg;
        }
        return re;
    }
}

class Solution {
    public int cuttingRope(int n) {
        int[] ans = new int[n+1];
        for(int i=0;i<=n;i++){
            ans[i]=0;
        }
        return cuttingRopeHelp(ans,n);
    }
    public int cuttingRopeHelp(int[] ans,int n){
        // 特殊情况
        if(n == 2){
            return 1;
        }
        if(ans[n]!=0){
            return ans[n];
        }
        int res = 0;
        for(int i = 2; i < n; i++){
            res = Math.max(res, Math.max(i * cuttingRopeHelp(ans,n-i), i * (n-i)));
        }
        ans[n]=res;
        return res;

    }
    
}