JZ67-剪绳子

class Solution {
    public int cutRope(int target) {
        if (target == 2) {
            return 1;
        } else if (target == 3) {
            return 2;
        }
        return helper(target);
    }

    private int helper(int n) {
        if (n <= 4) {
            return n;
        }
        int ret = 0;
        for (int i = 1; i < n; i++) {
            ret = Math.max(ret, i * helper(n - i));
        }
        return ret;
    }
}

class Solution2 {
    public int cutRope(int target) {
        int[] dp = new int[target + 1];
        dp[1] = 1;
        for (int i = 2; i <= target; i++) {
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), dp[j] * (i - j)));
                //              直接不分开  分成 j i-j(都 不 继续下分)  分成 j(继续下分)  i-j
            }
        }
        return dp[target];
    }
}