剑指offer_14_剪绳子

public static int cut(int length) {
    if(length < 2) {
        return 0;
    }
    if(length == 2) {
        return 1;
    }
    if(length == 3) {
        return 2;
    }
    int[] storage = new int[length + 1];
    // 初始化、这四个存的不是最优解而是用于计算的参数
    storage[0] = 0;
    storage[1] = 1;
    storage[2] = 2;
    storage[3] = 3;
    // 定义一个变量来存储最大值
    int max = 0;
    // 从第四米开始storage存的是最优解
    for (int i = 4; i <= length; i++) {
        // 从小到大开始把每个子问题最优解存在数组里
        for (int j = 1; j <= i / 2; j++) {
            int multiply = storage[j] * storage[i - j];
            if (multiply > max) {
                max = multiply;
            }
        }
        storage[i] = max;
    }
    return storage[length];
}

public static int cut(int length) {
    if(length < 2) {
        return 0;
    }
    if(length == 2) {
        return 1;
    }
    if(length == 3) {
        return 2;
    }
    // 记录要剪成3m一段的段数
    int three = length / 3;
    // 余下1m说明要腾出来一段凑4m来剪两个2m
    if (length - three * 3 == 1) {
        // 腾出
        three--;
    }
    // 要剪成2m的段数
    int two = (length - three * 3) / 2;
    return (int)(Math.pow(3,three) * Math.pow(2,two));
}