整数拆分原则（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]; } }

参考

官方题解-整数拆分