力扣343.整数拆分
343.整数拆分
给定一个正整数 n
,将其拆分为 k
个 正整数 的和( k >= 2
),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
1 | 输入: n = 2 |
示例 2:
1 | 输入: n = 10 |
提示:
2 <= n <= 58
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/integer-break/description/
思路
方法一:动态规划
dp
数组代表
方法二:数学
这个方法来自于美版的美版的大佬StefanPochmann:
You're making it pretty complicated.
If an optimal product contains a factor f >= 4, then you can replace it with factors 2 and f-2 without losing optimality, as 2*(f-2) = 2f-4 >= f. So you never need a factor greater than or equal to 4, meaning you only need factors 1, 2 and 3 (and 1 is of course wasteful and you'd only use it for n=2 and n=3, where it's needed).
For the rest I agree, 33 is simply better than 22*2, so you'd never use 2 more than twice.
正整数
简单地说,假设最优结果中包含因子
又因为
所以可以推导出永远不会使用
我们可以直观的知道,
数学归纳法可以得到上述结果。这里贴上力扣(Leetcode)官方题解
实现代码
动态规划:
1 | class Solution { |
- 时间复杂度:
- 空间复杂度:
数学
1 | class Solution { |
- 时间复杂度:
- 空间复杂度:
该封面图片由simardfrancois在Pixabay上发布