题目描述

解题思路

dp

https://www.yuque.com/jugelizi-rxt6d/dqbihl/dz2ygn#UjBKJ

数学推断

具体为什么分为3段，数学推理参照：https://leetcode.cn/leetbook/read/illustration-of-algorithm/5vyva2/
可以划分为3段：

• 最优为3，当余数为0之后，把绳子尽可能切为多个长度为 3 的片段，留下的最后一段绳子的长度可能为 0,1,2 三种情况。
• 当剩下1的时候，此时与1相乘还不如把他加上，例如：331<3*(3+1)一份 3 + 1 替换为 2 + 2，因为 2×2>3×1。
• 当剩下2的时候，此时可以直接相乘，因为乘2肯定比原来大。

  public int cuttingRope(int n) {
    if (n <= 3) return n - 1;
    int a = n / 3, b = n % 3;
    if (b == 0) return (int) Math.pow(3, a);
    if (b == 1) return (int) Math.pow(3, a - 1) * 4;
    if (b == 2) return (int) Math.pow(3, a) * 2;
    return 0;
  }