• 剪绳子
    • 题目
    • 解题思路

    剪绳子

    题目

    给定一根长度为n的绳子,请把绳子剪成m段(m、n都是整数,n>1并且m>1),每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0]* k[1] * … *k[m]可能的最大乘积是多少?

    解题思路

    1. 尽可能剪长度为 3 的绳子
    2. 当长度剩下的为 4 时,不能再减去 3,而是 2*2
    1. public int cutRope(int n) {
    2. if (n < 2) return 0;
    3. if (n == 2) return 1;
    4. if (n == 3) return 2;
    5. int timesOf3 = n / 3;
    6. if (n - timesOf3 * 3 == 1) {
    7. timesOf3 = 1;
    8. }
    9. int timesOf2 = (n - (timesOf3 * 3)) / 2;
    10. return (int) (Math.pow(3, timesOf3) * Math.pow((2), timesOf2));
    11. }