整数拆分原则（LeetCode-343. 整数拆分 – 题解分析）

题目来源

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   

   

   

。

提示:

2 <= n <= 58

题解分析

本题整数拆分的核心问题是如何定义状态方程的转移

     

     

     。状态方程的定义是比较简单的 




 




 




，dp[i]就表示i拆分后可以得到的最大乘积
  




  




  



。对于dp[i]的状态转移来说   

   

   

，需要考虑以下两种情况：

i可以拆分为j和i-j

     

     

     ，i-j无需再次拆分
  




  




  



，此时的乘积为：j * (i - j) i可以拆分为j和i-j  


  


  


，将i-j再次拆分 
     
     
    ，此时的乘积为：j * dp[i - j]

为了求得最大乘积

   




   




   


，需要从1开始遍历上述的j 



 



 



，在遍历的过程中不断更新dp[i]为最大值  


  


  


。

结果只需要返回dp[n]即可               ，也就是将n进行拆分后的最优结果 
     
     
    。

java实现

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

参考

官方题解-整数拆分