343.integer-break.md

343. 整数拆分

1. 描述

   • 给定一个正整数 n，
   • 将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。
   • 返回你可以获得的最大乘积。

2. 思路：动态规划

   • 定义：dp[i]表示，将正整数 i 拆分成至少两个正整数的和之后，这些正整数的最大乘积。

   • 初始化： 0不是正整数，1是最小的正整数，0和1都不能拆分。

     • 因此 dp[0] = dp[1] = 0。

   • 转移方程：

     • 假设对正整数 i（2 ≤ i ≤ n）拆分出的第一个正整数是 j（1 ≤ j < i）
     • 将 i 拆分成 j 和 i−j 的和，两种情况：
       • i-j 不再拆分成多个正整数，此时的乘积是 j×(i−j)；
       • i-j 继续拆分成多个正整数，此时的乘积是 j×dp[i−j]。
     • 所以，dp[i] = max(j×(i−j), j×dp[i−j])

   • 最后，返回dp[n]。

3. 实现

   class Solution {
   public:
       int integerBreak(int n) {
           vector<int>dp(n+1,0);
           int i,j;
           for(i=2; i<=n; i++){
               for(j=1; j<= i-1; j++){
                   dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j]));
               }
           }
           return dp[n];
       }
   };