解法一：动态规划

尤其注意！！
最开始的几个特殊值！！
n==2, return 1,
n==3, return 2.
验证了最开始的这些特殊值，循环才能平稳地走下去。

注意,如果用这种写法，dp[i]中储存的元素不能小于i本身。
然而只有n==4时，2*2=4才不小于4，所以要手动填充dp[1],dp[2],dp[3]。

public class Solution {
    public int cutRope(int target) {
        if(target==2) return 1;
        if(target==3) return 2;
        int[] dp=new int[target+1];
        dp[1]=1; dp[2]=2; dp[3]=3; 
        for(int i=4; i<target+1; i++){
            for(int j=1; j<i; j++)
                dp[i]=Math.max(dp[i], dp[i-j]*j);
        }
        return dp[target];
    }
}

解法二：数学公式法

非原创，原出处见
https://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8?answerType=1&f=discussion
速度比动态规划快一倍。
实在是太强了！

import java.util.*;
public class Solution {
    public int cutRope(int target) {
        if(target<=0) return 0;
        if(target==1 || target == 2) return 1;
        if(target==3) return 2;
        int m = target % 3;
        switch(m){
            case 0 :
                return (int) Math.pow(3, target / 3);
            case 1 :
                return (int) Math.pow(3, target / 3 - 1) * 4;
            case 2 :
                return (int) Math.pow(3, target / 3) * 2;
        }
        return 0;
    }
}