303.整数拆分

343. 整数拆分 - 力扣（LeetCode）

class Solution {public int integerBreak(int n) {int[] dp=new int[n+1];dp[2]=1;for(int i=3;i<=n;i++){for(int j=1;j<=i-j;j++){dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));}}return dp[n];}
}

class Solution(object):def integerBreak(self, n):dp = [0] * (n + 1)dp[2] = 1for i in range(3, n + 1):for j in range(1, i // 2 + 1):  # 修改为 i // 2 + 1dp[i] = max(dp[i], max(j * (i - j), j * dp[i - j]))return dp[n]