剪绳子

给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，2≤n≤58 并且 m≥2）。

每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少？

例如当绳子的长度是8时，把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。

样例 输入：8 输出：18

DP

时间复杂度O(n^2)

class Solution { public int integerBreak(int n) { int[] dp = new int[n+1]; for(int i = 2; i <= n; i++) for(int j = 1; j < i; j++) dp[i] = Math.max(dp[i], Math.max(j * (i-j), j * dp[i-j])); return dp[n]; } }

数学

时间复杂度O(n)

class Solution { int integerBreak(int n) { if (n <= 3) { return 1 * (n - 1); } int res = 1; if (n % 3 == 1) { res = 4; n -= 4; } else if (n % 3 == 2) { res = 2; n -= 2; } while (n > 0) { res *= 3; n -= 3; } return res; } }