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

    剪绳子

    题目

    给定一根长度为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;
    4.     if (n == 2) return 1;
    6.     if (n == 3) return 2;
    8.     int timesOf3 = n / 3;
    10.     if (n - timesOf3 * 3 == 1) {
    11.         timesOf3 = 1;
    12.     }
    14.     int timesOf2 = (n - (timesOf3 * 3)) / 2;
    16.     return (int) (Math.pow(3, timesOf3) * Math.pow((2), timesOf2));
    17. }