题解 | #剪绳子#

public class Solution {
    public int cutRope(int target) {
        if (target <= 1) {
            return target;
        }
        int[] nums = new int[target + 1];
        nums[1] = 1;
        nums[0] = 1;
        for (int i = 2; i <= target; i++) {
            int max = i;
            for(int j=0;j<=i/2;j++){
                int temp = nums[j]*nums[i-j];
                if(temp>max){
                    max = temp;
                }
            }
            nums[i]=max;
        }
        return nums[target];
    }
}

解题思想：

本题的解答思路就是每个⻓度的绳⼦，要么最⻓的情况是不剪开（⻓度是本身），要么⻓度是剪开两段的乘积。因此每个⻓度 length 都需要遍历两个相加之后等于length 的乘积，取最⼤值。