正の整数 n が与えられたとき、それを少なくとも2つの正の整数の和に分割し、それらの整数の積を最大化しなさい。 得られる最大の積を返しなさい．
例題:
- 例1
: 2
: 1
: 2 = 1 + 1, 1 × 1 = 1
- 例2
: 10
: 36
: + 4, 3 × 3 × 4 = 36
内容:
nは2以上58以下と仮定してください。
推論
n個の数字に分割され、nは固定されていない このタイプの問題：ルールは確実、開始条件は不確定。
- 動的計画法
- 再帰
動的計画法
nを列挙し、dpは異なるnの結果値を記録し、dp[n]はクエリー結果：
- 分割する整数の数を決定：<=i<=n2<=i<=n
- dp[i]はiで分割された整数の積の最大値。
- 2つ以上のj,dp[i - j]を分割 -> dp[i - j]は2つ、つまりより多くの部分集合を分割
- 2つのjの分割，i-j
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function (n) {
let dp = Array(n + 1).fill(1)
for (let i = 2; i <= n; i++) {
let curMax = 0
for (let j = 1; j < i; j++) {
curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]))
}
dp[i] = curMax
}
return dp[n]
}
再帰
- パラメータで分割する整数を指定します。
- 終了条件：
- 既に分割された配列に遭遇した場合
再帰のロジックは基本的にダイナミック・プログラミングと同じです：
- 数字jを分割
- i-jに属する数字は、単独で数字として成り立つことも、分割され続けることもできます。
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function (n) {
let dp = Array(n + 1).fill(1)
function dfs(n){
if (dp[n]) return dp[n];
let curMax = 0;
for (let i = 1; i < n; i++) {
curMax = Math.max(curMax, i * (n - i), i * dfs(n - i));
}
return dp[n] = curMax;
};
return dp[n]
}
最適化された動的計画法
/**
* @param {number} n
* @return {number}
*/
var integerBreak = function (n) {
if (n < 4) return n - 1;
let dp = Array(n + 1).fill(1)
for (let i = 3; i <= n; i++) {
dp[i] = Math.max(Math.max(2 * (i - 2), 2 * dp[i - 2]), Math.max(3 * (i - 3), 3 * dp[i - 3]));
}
return dp[n];
}
ブログ：
出版：The Pit's Little Bookie
