整数拆分 | LeetCode-343 | 动态规划

动态规划练习题

---

LeetCode链接：343. 整数拆分

---

1.题目描述

给定一个正整数 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

2.题解

2.1 动态规划

class Solution {
    // 定义一个公共方法 integerBreak，它接受一个整数 n 作为参数
    public int integerBreak(int n) {
        // 初始化一个动态规划数组，长度为 n + 1，并且所有元素初始化为 0
        int[] dp = new int[n+1];

        // 当 n 为 2 时，最大乘积为 1（2 = 1 * 1）
        dp[2] = 1;

        // 从 3 开始遍历到 n，因为当 n = 2 时的情况已经处理过了
        for(int i = 3; i <= n; i++) {
            // 遍历所有可能断裂的位置
            for(int j = 1; j < i - 1; j++) {
                // 确保断裂后的两个数都大于等于 2，即至少有一个断点
                // 更新 dp[i] 的值为三个值中的最大者：
                // 1. 当前 dp[i] 的值
                // 2. 断裂位置 j 和剩余部分 i - j 的乘积
                // 3. 断裂位置 j 和剩余部分断裂后的最大乘积 dp[i - j]
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
            }
        }

        // 返回 n 断裂的最大乘积
        return dp[n];
    }
}

2.2 数论

• 解题思路：

  • 设将整数$n$拆分为$a$个小数字：

    $n=n_1+n_2+…+n_a$

  • 本题等价于求解：

    $\max(n_1\times n_2\times…\times n_a)$

以下数学推导总体分为两步：① 当所有拆分出的数字相等时，乘积最大。② 最优拆分数字为 3 。

拆分规则：

1. 最优： 3 。把数字 n 可能拆为多个因子 3 ，余数可能为 0,1,2 三种情况。
2. 次优： 2 。若余数为 2 ；则保留，不再拆为 1+1 。
3. 最差： 1 。若余数为 1 ；则应把一份 3+1 替换为 2+2，因为 2×2>3×1。

算法流程：

1. 当 n≤3 时，按照规则应不拆分，但由于题目要求必须拆分，因此必须拆出一个因子 1 ，即返回 n−1 。
2. 当n>3时，求n除以3的 整数部分a和 余数部分b（即n=3a+b），并分为以下三种情况：
   • 当 b=0 时，直接返回 3a；
   • 当 b=1 时，要将一个 1+3 转换为 2+2，因此返回$3^{a−1}×4$；
   • 当 b=2 时，返回$3^a×2$

• 代码实现：

  class Solution {
      // 定义一个公共方法 integerBreak，它接受一个整数 n 作为参数
      public int integerBreak(int n) {
          // 如果 n 小于或等于 3，直接返回 n - 1 （除了 n = 2 时，其本身已经是最大乘积）
          if (n <= 3) return n - 1;
  
          // 计算 n 除以 3 的商
          int a = n / 3;
          
          // 计算 n 除以 3 的余数
          int b = n % 3;
  
          // 如果 n 能够被 3 整除，即余数为 0，则结果就是 3 的 a 次方
          if (b == 0) return (int)Math.pow(3, a);
  
          // 如果余数是 1，表示可以将一个 3 替换为 4 （因为 3 + 3 变为 2 + 2 + 3），从而得到更大的乘积
          if (b == 1) return (int)Math.pow(3, a - 1) * 4;
  
          // 如果余数是 2，则直接将两个 3 中的一个替换为 2 （因为 3 * 3 变为 3 * 2），这样不会减少乘积
          return (int)Math.pow(3, a) * 2;
      }
  }