DP解法

提前把绳子等于2、3的最大值写入表，之后向后推算最大值。

$O(n^2)$

class Solution {
  public int maxProductAfterCutting(int n) {
        if (n < 2)
            return 0;
        // 至少剪2段
        if (n == 2) return 2;
        if (n == 3) return 3;
        int[] dp = new int[n + 1];
        dp[2] = 2;
        dp[3] = 3;
      for (int i = 4; i <= n; i++) {
            for (int j = 2; j <= i / 2; j++) {
                dp[i] = Math.max(dp[i], dp[j] * dp[i - j]);
            }

        }
        return dp[n];
    }
}

贪婪解法

尽可能多剪3，不够换剪2

剪出2的次数是有限个0,1,2. 主要取决于剪出3的次数，求3^times过程。times约有N/3次, 时间复杂度O(n/3)=O(n)

  public int maxProductAfterCutting(int n) {
        if(n <= 3) return 1*(n-1);
        // 先确定3的次数
        int threeTimes  = n/3;
        if (n%3 == 1)
        {
            threeTimes--;
        }
        // 后有确定3的次数确定2的次数
        int twoTimes = (n - 3 * threeTimes)/2;
        int res = 1;
        while (threeTimes>0){
            res  *=3;
            threeTimes--;
        }
        while (twoTimes>0){
            res *= 2;
            twoTimes--;
        }
        return  res;
    }