美文网首页
面试题14: 剪绳子

面试题14: 剪绳子

作者: mark_x | 来源:发表于2019-10-10 01:02 被阅读0次
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));
    }

}

相关文章

  • 剪绳子

    《剑指offer》面试题14:剪绳子 题目:给你一根长度为n的绳子,请把绳子剪成m段 (m和n都是整数,n>1并且...

  • 面试题14:剪绳子

    给你一根长度为 n 的绳子,请把绳子剪成 m 段(m、n 都是整数,并且)。每段的绳子的长度记为、、……、。可能的...

  • 面试题14:剪绳子

    牛客上面没有这道题,自己做,书上再解释的时候,没有很详细的解释代码初始化部分,想了好久。

  • 面试题14:剪绳子

    前序动态规划与贪婪算法如果面试题是求一个问题的最优解(通常是最大值和最小值),而且该问题可以分解为若干个子问题,并...

  • 面试题14: 剪绳子

  • 面试题14:剪绳子

    题目:给你一根长度为n的绳子,请把绳子剪成m段(m、n都是整数,n>1并且m>1),每段绳子的长度即为k[0],k...

  • 面试题14:剪绳子

    题目 给你一根长度为n的绳子,请把绳子剪成m段(m,n都是整数,n>1且m>1)。每段绳子的长度记为k[0],k[...

  • 面试题14:剪绳子

    题目 :给你一根长度为n的绳子,请把绳子剪成整数长的m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k...

  • 剑指offer第二版-14.剪绳子(动态规划)

    本系列导航:剑指offer(第二版)java实现导航帖 面试题14:剪绳子 题目要求:给你一根长度为n的绳子,请把...

  • 14 剪绳子

    注:1到3是特殊情况

网友评论

      本文标题:面试题14: 剪绳子

      本文链接:https://www.haomeiwen.com/subject/nknnpctx.html