Integer Break (M)
題目
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
Example 1:
Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.
Example 2:
Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.
Note: You may assume that n is not less than 2 and not larger than 58.
題意
將一個正整數拆成至少兩個正整數的和，使得拆分出來的正整數之積最大，
思路
經驗告訴我們，當一個正整數被拆成n個整數時，積最大時這n個整數應該相等(或相近)，如10拆成2個整數時，5*5最大，拆成3個時，3*3*4最大，拆成4個時，2*2*3*3最大…所以我們只要從n=2開始遞增，求出積變化情況的極大值即可，
打一張表找一下規律：
| 正整數n | 最大積 |
|---|---|
| 2 | 1*1 |
| 3 | 1*2 |
| 4 | 2*2 |
| 5 | 3*2 |
| 6 | 3*3 |
| 7 | 3*4 |
| 8 | 3*3*2 |
| 9 | 3*3*3 |
| 10 | 3*3*4 |
| 11 | 3*3*3*2 |
| 12 | 3*3*3*3 |
| 13 | 3*3*3*4 |
可以看到當n大于4時，最大積的情況都是將n拆成盡可能多的3，且除3外只能有一個2或者一個4，該規律的證明可參考《平分一個數，使得各份相乘所得到的積最大》，
也可以使用動態規劃：dp[i]代表正整數i拆分后能得到的最大積，i可以被拆分為2個或更多的整數，拆分為兩個時得到的積為j*(i-j)，拆分為多個時可得到的積為j*dp[i-j]，狀態轉移方程為 \(dp[i]=max(dp[i],\ max(j*(i-j),\ j*dp[i-j]))\)，
代碼實作
Java
極大值
class Solution {
public int integerBreak(int n) {
int pre = 0;
int count = 2;
while (count <= n) {
int num = n / count;
int remain = n % count; // 存在余數時，要將余數中的每一個1都分配到num上以求積最大化
int cur = (int) Math.pow(num, (count - remain)) * (int) Math.pow((num + 1), remain);
if (cur >= pre) {
pre = cur;
} else {
return pre;
}
count++;
}
return pre;
}
}
找規律
class Solution {
public int integerBreak(int n) {
if (n == 2 || n == 3) {
return n - 1;
}
int cnt3 = n / 3;
int remain = n % 3;
if (remain == 1) {
return (int) Math.pow(3, cnt3 - 1) * 4;
} else {
return (int) Math.pow(3, cnt3) * (remain == 2 ? 2 : 1);
}
}
}
動態規劃
class Solution {
public int integerBreak(int n) {
int[] dp = new int[n + 1];
Arrays.fill(dp, 1);
for (int i = 3; 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];
}
}
參考
[LeetCode] 343. Integer Break 整數拆分
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/36574.html
標籤：其他