- public class Solution {
- public int cutRope(int target) {
- if(target <= 1) return 0;
- if(target == 2) return 1;
- if(target == 3) return 2;
- int x=target/3;
- int y=target%3;
- if(y == 1) {
- return 4*(int)Math.pow(3,x-1);
- }
- else if(y == 2){
- return 2*(int)Math.pow(3,x);
- }else {
- return (int)Math.pow(3,x);
- }
- }
- }
动态规划也可以
将这个长度分为两半 当前长度乘积最大就等于两半分别的乘积最大 -》最优子结构和子问题重叠
- public class Solution {
- public int cutRope(int target) {
- if(target <= 1) return 0;
- if(target == 2) return 1;
- if(target == 3) return 2;
- int[] project=new int[target+1];
- project[0]=0;
- project[1]=1;
- project[2]=2;
- project[3]=3;
- for(int i = 4;i <= target;i ++){
- int max=0;
- for(int j = 1;j <= i/2;j ++){
- max=Math.max(max,project[j]*project[i-j]);
- }
- project[i] = max;
- }
- return project[target];
- }
- }
来源: http://www.bubuko.com/infodetail-3458964.html