题目 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]
标签:遍历,乘积,整数,拆分,343,时为,dp
From: https://www.cnblogs.com/edkong/p/16830511.html