面试题14: 剪绳子

package cn.zxy.interview;

/**
 * 分析:
 * 动态规划典型题
 * 例如要求长度为8的绳子怎么剪得到的乘积最大, 只需要算一层, 将绳子剪成两段
 * 分别是(1,7)  (2,6)  (3,5)  (4,4)  这里我们假设一个前提就是分成的这些小段乘积已经有最优解
 * 只要是小段的乘积最大, 大段的乘积一定最大
 * 这就是动态规划法的核心之一: 整体问题的最优解依赖于每个子问题的最优解
 *
 * 一个细节:
 * 为什么要从4开始计算得到最优, 而不是大一点比如5, 也不是小一点比如3
 * 因为从4以及4以后的数, 其分段最大乘积一定大于本身 分段求最优才有意义
 * 比如5-->(2*3=6>5)
 *
 * 如果用递归 会出现子问题求解重复 因此使用循环
 */


public class A14_CutRope {
    public static int maxProductAfterCutting(int length){
        //边界情况 可以理解为无法用动态规划求出
        if(length < 2) return 0;
        if(length == 2) return 1;
        if(length == 3) return 2;

        //大于等于4的情况
        int[] products = new int[length + 1];
        products[0] = 0;
        products[1] = 1;
        products[2] = 2;
        products[3] = 3;

        for (int i = 4; i <= length; i++) {
            //剪一次
            int max = 0;
            for(int j = 1; j <= i/2; j++){
                int temp = products[j] * products[i-j];
                max = Math.max(max, temp);
            }
            products[i] = max;
        }

        return products[length];
    }

    /**
     * 贪婪算法
     * 尽可能多的剪去长度为3的绳子段
     *
     */
    public static int greedAlgs(int length){
        if(length < 2) return 0;
        if(length == 2) return 1;
        if(length == 3) return 2;

        int timesOf3 = length / 3;

        //可能剩下0, 1, 2; 如果剩下1, 说明最后一剪子把长度为4剪成了1,3两段,
        // 而剩余长度为4时剪成2,2结果才是最优的4>1*3
        if((length - 3 * timesOf3) == 1){
            timesOf3--;
        }

        //如果是0, timeOf2 = 0;  如果剩下是2, timeOf2 = 1
        int timesOf2 = (length - 3 * timesOf3) / 2;

        int max = (int)Math.pow(3, timesOf3) * (int)Math.pow(2, timesOf2);
        return max;
    }

    public static void main(String[] args) {
        int num = 24;

        System.out.println(maxProductAfterCutting(num));

        System.out.println(greedAlgs(num));
    }

}