专业的上海网站建设公司/网络培训机构排名前十

动态规划

如果面试题是求一个问题的最优解（通常是最大值或者最小值），而且该问题能够分解成若干个子问题，并且子问题之间还有重叠的更小的子问题，就可以考虑用动态规划来解决这个问题。一般为了避免重复计算，从下而上用数组记录子问题的最优解。
**关键：**大问题 – 分解 --> 小问题，小问题最优解组合能够得到整个问题的最优解，就是动态规划

问题：给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

动态规划

• 时间复杂度O(n^2)
• 空间复杂度O(n)

// 动态规划
public static int cuttingRope(int n) {// 先把特殊情况考虑完全if (n < 2) {return 0;}if (n == 2) {return 1;}if (n == 3) {return 2;}int[] array = new int[n + 1];// 0，1，2，3是初始值，特殊考虑过，绳子剪到当前长度应该给的值，比如长度5 = 2 + 3，这个3表示绳子长度为3array[0] = 0;array[1] = 1;array[2] = 2;array[3] = 3;for (int i = 4; i <= n; i++) {int max = 0;for (int j = 0; j <= i/2; j++) {int product = array[j] * array[i - j];if (max < product) {max = product;}}array[i] = max;}return array[n];
}

贪心

当绳子长度 n >= 5 时，尽可能多的剪长度为 3 的绳子，当绳子长度 n = 4 时，只剪成长度为 2 的绳子。
可以用数学证明，这种贪心是满足条件的

public static int cuttingRope(int n) {// 先把特殊情况考虑完全if (n <= 3){return n - 1;}int res = 1;while (n > 5) {res *= 3;n -= 3;}if(n == 5) {res *= 6;}else { // n只可能等于 4 或者 3 res *= n;}return res;
}