1. 题目:
给定一个正整数 n ,将其拆分为 k 个 正整数 的和( k >= 2 ),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
2. 我的代码:
class Solution: def integerBreak(self, n: int) -> int: # dp数组定义 dp = [0] * (n + 1) # dp数组初始化 dp[0] = 0 dp[1] = 0 dp[2] = 1 # 遍历 for i in range(3, n + 1): for j in range(1, i // 2 + 1): dp[i] = max(j * dp[i - j], dp[i], j * (i - j)) return dp[n]
动态规划最重要最需要理清楚的点:
- dp数组及其下标的含义
- 递推公式
- dp数组初始化
- 遍历顺序
这里,通过推理得到:
- dp数组的下标代表的是整数值,dp数组的值代表的是这个整数拆分后乘积的最大值
- 递推公式
j * dp[i - j]
表示拆分的情况,j * (i - j)
表示不拆分的情况,递推的每一步都需要把拆解方法都试一遍,第一个数字拆出来的范围就是1到i // 2,因为比i // 2大的话,i - j这个被拆的数就一定无法满足数字尽可能相同,要拆当然是拆大的。还要和之前拆的dp[i]比较一下,所以综合下来,递推公式就是:dp[i] = max(j * dp[i - j], dp[i], j * (i - j))
- dp数组的初始化:dp[0]肯定没有意义,dp[1]也没有意义,dp[2]等于1 * 1 = 1,因此给dp[0]和dp[1]都赋值为0,防止继续递推下去,如果递推下去就会0乘以任何数都是0
- 遍历顺序就是从3到n即可,最后输出的就是dp[n]