343. 整数拆分

1. class Solution:
2.     def integerBreak(self, n: int) -> int:
3.         dp=[0]*(n+1)
4.         dp[2]=1
5.         for i in range(3,n+1):
6.             for j in range(0,i//2+1):
7.                 dp[i]=max(j*(i-j),j*dp[i-j],dp[i])
8.         return dp[n]

很有意思的题

dp[i]=max(j*(i-j),j*dp[i-j],dp[i])中的dp[i]记录了在第二个for循环中dp[i]的最大值