模版题-动态规划-整数拆分 ( 思考过程非常重要 思考过程中发现需要记录一些东西 从而决定的动态规划 而不是一眼动态规划 )
- 版权声明：本站原创文章，于2026-05-11，由 管理员 发表。
- 转载请注明： 模版题-动态规划-整数拆分 ( 思考过程非常重要 思考过程中发现需要记录一些东西 从而决定的动态规划 而不是一眼动态规划 ) | CodeGarden
**思考过程非常重要 思考过程中发现需要记录一些东西 从而决定的动态规划 而不是一眼动态规划**
```python
class Solution:
# 给定一个正整数n，将其拆分为k个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。
# 返回可以获得的最大乘积 。
"""
-- 分析过程 --
# 1. 如果将n拆成两数相乘 x * y
for x in range( 1, n ):
y = n - x
# 2. x和y还可以拆成多个数相乘 还需要知道x和y拆分后的最大乘积
# n = 2, 1*1
# n = 3, 1*2, 2*1 => 1*dp(2),dp(2)*1
# n = 4, 1*3, 2*2, 3*1 => 1*dp(3), 2*dp(2), dp(2)*2, dp(2)*dp(2), dp(3)*1
# 其实到这里就知道如果记录 需要记录什么 dp(i)表示i拆分后的最大乘积
# 4 填充dp 实现递归公式
dp[ x ] = max( dp[ x ], dp)
"""
def integerBreak(self, n: int) -> int:
dp = [ 0 for _ in range( n + 1 ) ]
# dp[ 0 ]和dp[ 1 ]没什么含义 只是辅助初始化的 毕竟0和1都不可能拆分
dp[ 1 ] = 1
for i in range( 2, n + 1 ):
for x in range( 1, i ):
y = i - x
# 其中x和y 可以拆分也可以不拆分 所有情况取最大
dp[ i ] = max( dp[ i ], x * y, x * dp[ y ], dp[ x ] * y, dp[ x ] * dp[ y ] )
return dp[ n ]
```
为了整体性，代码中没有对边界进行优化，实际上拆分成x,y时会重复，边界可优化。如下：
```
...
for x in range( 1, i // 2 + 1 ):
...
```