题解 | #剪绳子#

public class Solution {
    public int cutRope(int target) {
        //因为绳长<=4的时候，取最大值就是它的本身
        int dp[]=new int[target+1];
        dp[1]=1;
        dp[2]=2;
        dp[3]=3;
        dp[4]=4;
        //从第五个开始遍历
        for(int i=5;i<=target;i++){
            //可以分成两大部分，一部分就是已保存的可以剪出来最大乘积，这个不管细分多少，这个部分已经包括了所有情况的最大乘积。另一部分就是这个最大乘积的剩余长度与这个乘积相乘。最后取当前最大乘积值
            for(int j=1;j<i;j++){
                dp[i]=Math.max(dp[i],j*dp[i-j]);
            }
        }
        return dp[target];
    }
}