题目:
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
1. 示例1
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
你可以假设 n 不小于 2 且不大于 58
返回它的最大深度 3 。
思路
拆成 n 个数,n 不固定
这种类型的题目:规则确定,起始条件不确定
动态规划
枚举 n,dp 记录不同 n 的结果值,dp[n]即查询结果:
/**
* @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]
递归的逻辑基本和动态规划一致:
/**
* @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];
}