0343. 整数拆分

0343. 整数拆分 #

  • 标签:数学、动态规划
  • 难度:中等

题目大意 #

给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。要求:返回可以获得的最大乘积。

解题思路 #

可以使用动态规划求解。

定义状态 dp[i] 为:拆分整数 i,可以获得的最大乘积为 dp[i]

j1 遍历到 i - 1,通过两种方式得到 dp[i]

  • (i - j) * j ,直接将 i 拆分为 i - jj,获取两者乘积。
  • dp[i - j] * j,将 i 中的 i - j 部分拆分,得到 dp[i - j],和 j ,获取乘积。

dp[i] 取两者中的最大值。遍历 j,得到 dp[i] 的最大值。

则状态转移方程为:dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)

最终输出 dp[n]

代码 #

1
2
3
4
5
6
7
8
class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0 for _ in range(n + 1)]
        dp[2] = 1
        for i in range(3, n+1):
            for j in range(1, i):
                dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)
        return dp[n]
本站总访问量  次  |  您是本站第  位访问者