第 14 题：剪绳子
说明：同 LeetCode 343 题。
传送门：AcWing 25. 剪绳子，牛客网 online judge 地址。
给你一根长度为
的绳子，请把绳子剪成
段（
并且
）。
每段的绳子的长度记为
k[0]、k[1]、……、k[m]。k[0]k[1] … k[m]可能的最大乘积是多少？例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。
样例：
输入：8
输出：18
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
分析：这道题在牛客网上没有 online judge ，我们可以去完成 LeetCode 上第 343 题检验自己的代码是否编写正确。
动态规划。关键在于画出树形结构图。
状态：dp[i]，这个状态就是题目中要我们求的。把整数 i 至少分割成 个部分，各个部分都大于
，它们的乘积。
状态转移方程：用 j 遍历 1，2，…, i -1 ，要么分割成两部分：i - j 和 j，要么是 j 和 dp[i-j]，取最大者。
Python 代码：dp[0] 这个位置没有使用
class Solution(object):
def maxProductAfterCutting(self, length):
"""
:type length: int
:rtype: int
"""
assert length > 1
dp = [0 for _ in range(length + 1)]
dp[1] = 1
for i in range(2, length + 1):
for j in range(1, i):
dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
return dp[length]
Java 代码：使用动态规划
class Solution {
public int integerBreak(int n) {
if (n <= 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
int max = 0;
for (int j = 1; j < i; j++) {
max = max3(max, j * (i - j), j * dp[i - j]);
}
dp[i] = max;
}
return dp[n];
}
private int max3(int num1, int num2, int num3) {
return Integer.max(Integer.max(num1, num2), num3);
}
public static void main(String[] args) {
Solution solution = new Solution();
int integerBreak = solution.integerBreak(8);
System.out.println(integerBreak);
}
}
Java 代码：使用贪心算法
class Solution2 {
public int integerBreak(int n) {
if (n <= 2) {
return 1;
}
if (n == 3) {
return 2;
}
if (n == 4) {
return 4;
}
// 接下来就是 n >= 5 的时候的逻辑了
int res = 1;
while (n > 4) {
res *= 3;
n -= 3;
}
res *= n;
return res;
}
public static void main(String[] args) {
Solution2 solution2 = new Solution2();
int integerBreak = solution2.integerBreak(8);
System.out.println(integerBreak);
}
}
LeetCode 343 题：整数拆分
传送门：343. 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。说明: 你可以假设 n 不小于 2 且不大于 58。
分析：这是一个很经典的问题。可以使用贪心算法。
贪心算法： 得到
，
，得到
，即
大于等于
的时候。
结论：不能包含 ，所有的加法因子只能有
和
，最多只有
个
，因此加法因子里没有
。
Java 代码：
class Solution2 {
public int integerBreak(int n) {
if (n <= 2) {
return 1;
}
if (n == 3) {
return 2;
}
if (n == 4) {
return 4;
}
// 接下来就是 n >= 5 的时候的逻辑了
int res = 1;
while (n > 4) {
res *= 3;
n -= 3;
}
res *= n;
return res;
}
public static void main(String[] args) {
Solution2 solution2 = new Solution2();
int integerBreak = solution2.integerBreak(8);
System.out.println(integerBreak);
}
}
C++ 代码：
