343 整数拆分

题目 343 整数拆分

给定一个正整数 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。

思路

注意：有障碍物的位置设置dp为0值即可，可以自己画图理解理解。

• 动规数组dp[i]及其的下标含义
  dp[i]：第i个数拆分后最大乘积值为dp[i]

• 递推公式
  1、一个整数至少分成两个数，假设分成j和i-j
  2、得到递推公式:dp[i] = max(dp[i], dp[j]*dp(i - j));

• 初始化
  当n=2时为1，n=3时为2

  还有一种在处理递推公式的情况，当n=2时为2，n=3时为3，就是当n=2或者3时不再切分，因为切分只会让数值乘积更小。当然这个推出来的结果，当n>=4时，其切分后最大乘积值肯定大于原值，找不到比原值小的特例。
  参考：https://www.bilibili.com/video/BV1Nt4y1D7gh/?spm_id_from=333.337.search-card.all.click&vd_source=d6067928eb906629adf6cc260761df74

• 遍历顺序
  遍历行从前往后

• 举例验证
  自己画图试试就行了

代码

class Solution:
    def integerBreak(self, n: int) -> int:
        if n==2: return 1
        if n==3: return 2
        # 记得是乘n+1，因为第n个数，其下标就是n
        dp = [0]*(n+1)
        dp[1] = 1
        dp[2] = 2
        dp[3] = 3
        for i in range(4, n+1):
            for j in range(1, n//2+1):  # 从切1个开始遍历，遍历到中间即可，以防奇数，可以加1
                dp[i] = max(dp[i], dp[j]*dp[i-j])
        return dp[n]