动态规划
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);
}
}