剪绳子_JAVA_中等

• 设绳子长为n的解为f(n)，则
  
  即长为n的解 为 长为j的解 和 长为n-j的解 的乘积的最大值

public class Solution {
    public int cutRope(int target) {
        int[] cache = new int[target + 1];
        // 求绳子长为i的解
        for(int i = 1; i <= target; i++) {
            // 绳子长为i的解可化为 长为i-j与j的解的乘积最大值
            int max = i;
            for(int j = 1; j  <= i / 2; j++) {
                max = Math.max(max, cache[i - j] * cache[j]);
            }
            cache[i] = max;
        }
        return cache[target];
    }
}