动态规划+记忆化搜索

public class Solution {

public int cutRope(int target) {
     if(target == 2){
         return 1;
     }

     if(target == 3){
         return 2;
     }

    int[] mem = new int[target+1];

    for(int i = 0 ; i<mem.length;i++){
        mem[i] = -1;
    }

    return func(target,mem);
}

private int func(int n,int[] mem){
    int max = 0;
    if(n==2){
        return 2;
    }
    if(n==3){
        return 3;
    }

    if(mem[n]!= -1){
        return mem[n];
    }
    for(int i = 2; i<= n-2; i++){
        max = max(func(i,mem)* func(n-i,mem),max);
    }

    mem[n] = max;

    return mem[n];
}


private int max(int i, int j){
    return i>=j ? i:j;
}

}