【剑指offer】剪绳子

贪心解法
把绳长target剪成i段的最大值为：Math.pow(n, i - c) * Math.pow(n + 1, c)
如：target=8 i=3时，ans=2^1*3^2
然后在剪成2段、3段...x段中取最大值即可。

public class Solution {
    public int cutRope(int target) {

        int result = 0;
        for (int i = 2; i <= target; i++) {
            int n = target / i, c = target % i;
            int ans = (int) (Math.pow(n, i - c) * Math.pow(n + 1, c));
            if (ans > result) {
                result = ans;
            }
        }
        return result;
    }
}

DP解法
f[i]表示长度为i的绳子的乘积最大值。
f[i] = Max{f[j]*f[i-j]} 0<j<i

public class Solution {
    public int cutRope(int target) {

        int[] dp = new int[target + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= target; i++) {
            if (i != target) { // 当i!=target时，长度为i的段也可以不分割！
                dp[i] = i;
            }
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
            }
        }
        return dp[target];
    }
}