题目

image.png

思路

  • 在剪绳子中我们已经知道，每个数切分成2或3时乘积最大，但是由于有取余操作，所以无法再像剪绳子一样，使用动态规划，但222<3*3，所以更准确来说尽可能切分为3时数字最大，这时考虑贪心算法的思路，不断切割为3，直到小于等于4，当等于4时，切割为2更大

    代码

    1.   public int cuttingRope(int n) {
    2.       if (n <= 3) return n - 1;
    3.       long res = 1, b = 1000000007;;
    4.       while (n > 4) {
    5.           res *= 3;
    6.           res %= b;
    7.           n -= 3;
    8.       }
    9.       return (int) (res * n % b);
    10.   }
    剪绳子 II