0%

leetcode每日一题-整数拆分

Posted on In ,

整数拆分

image1

方法一：动态规划

记$dp[i]$为将正整数$i$拆分成至少两个正整数的和之后，这些正整数的最大乘积，边界情况是$dp[0]$和$dp[1]$，0不是正整数，1不能拆分，所以$dp[0]=dp[1]=0$。当$i>=2$时，假设对正整数$i$拆分的第一个数为$j(1<=j<i)$，那么有两种情况，第一种是不继续拆分，那么结果就是$j \times (i-j)$，如果继续拆分，那么结果就是$j \times dp[i-j]$，两者取较大值，结果返回$dp[n]$。

1
class Solution {
2
    public int integerBreak(int n) {
3
        int[] dp = new int[n+1];
4
        for(int i=2; i<=n; i++){
5
            int tmp = 0;
6
            for(int j=1; j<i; j++){
7
                tmp = Math.max(tmp,Math.max(j*(i-j), j*dp[i-j]));
8
            }
9
            dp[i] = tmp;
10
        }
11
        return dp[n];
12
    }
13
}

复杂度分析：

  • 时间复杂度：$O(n^2)$。
  • 空间复杂度：$O(n)$。

方法二：数学

可以找下规律，比如从7到10，应该如何拆分，可以看到7应该拆分成$3 \times 2 \times 2$，8应该是$3 \times 3 \times2$，9应该是$3 \times 3 \times 3$，10应该是$3 \times 3 \times 2 \times 2$，我们大概能猜出规律，要得到乘积最大的数，应该尽可能多地拆分出3。下图是数学证明法：

image2

如果余数是0，那么就全部拆分为3；如果余数是1，那么就将最后一个3和余数拆分成两个2，因为$2 \times 2> 3 \times 1$；如果余数是2，就直接乘。

1
class Solution {
2
    public int integerBreak(int n) {
3
        if (n <= 3) {
4
            return n - 1;
5
        }
6
        int quotient = n / 3;
7
        int remainder = n % 3;
8
        if (remainder == 0) {
9
            return (int) Math.pow(3, quotient);
10
        } else if (remainder == 1) {
11
            return (int) Math.pow(3, quotient - 1) * 4;
12
        } else {
13
            return (int) Math.pow(3, quotient) * 2;
14
        }
15
    }
16
}

复杂度分析：

  • 时间复杂度：$O(1)$。
  • 空间复杂度：$O(1)$。