题目描述
给定一个正整数 nn,将它拆分成最少两个数的和,使得这些数的乘积最大。请返回最大的乘积。
注意: n 不小于 2 且不大于 58
样例
给定 n = 2;
输出:1
解释:2 = 1 + 1,至少表示成两个数的和;
给定 n = 10;
输出 36
解释:10 = 3 + 3 + 4;
算法1
(自顶向下动态规划)
这道题其实很明显是可以用递归的,但是我当时第一次是超时的。
但是,仔细分析递归树,其实可以用map来存计算过的节点,那么就可以通过。
Java 代码
class Solution {
Map<Integer, Integer> memo = new HashMap<>();
public int integerBreak(int n) {
return dfs(n);
}
private int dfs(int n) {
if (n == 0) {
return 0;
} else if (n == 1) {
return 0;
} else if (n == 2) {
return 1;
}
if (memo.get(n) != null && memo.get(n) > 0) {
return memo.get(n);
}
int res = 0;
for (int i = 1; i <= n - 1; i++) {
res = Math.max(res, Math.max(i * (n - i), i * dfs(n - i)));
}
memo.put(n, res);
return res;
}
}