动态规划

public class Solution {
    public int cutRope(int target) {
      
        // 返回不符合子问题求解逻辑的case
        if(target == 2){
            return 1;
        }
        
        if(target == 3){
            return 2;
        }
        
        // 定义结果集,稍后的循环会使用这里的结果集
        int[] result = new int[target+1];
        result[0] = 0;
        result[1] = 1;
        result[2] = 2;
        result[3] = 3;
        
        
        // 循环求解target的子问题
        int max = 0;
        for(int i = 4; i<= target; i++){
            max = 0;
          
            // 具体求解子问题的结果,并保存到结果集result中
            for(int j = 1; j<= i/2; j++){
                if(result[j] * result[i-j] > max){
                    max = result[j] * result[i-j];
                }
                
            }
            result[i] = max;
        }
        
        return result[target];
    }
}

贪心算法

public class Solution {
    public int cutRope(int target) {
        
        // 特殊case返回
        if(target == 2){
            return 1;
        }
        
        if(target == 3){
            return 2;
        }
        
        int timesOf3 = target / 3;
        
        int timesOf2 = 0;
        if((target % 3) == 1){
            timesOf3 = timesOf3 - 1;
            timesOf2 = 2;
        }else if((target % 3) == 2){
            timesOf2 = 1;
        }
        
        // 求 3的timesOf3次幂 * 2的timesOf2次幂 的乘积
        return (int)Math.pow(3,timesOf3) * (int)Math.pow(2,timesOf2);
        
        
    }
}