Ricky.L的随笔
0%

LeetCode.343.整数拆分（中等）

发表于 更新于 分类于 Disqus：

题目

LeetCode.343.整数拆分（中等）

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

题解

题目已经说出了步骤，直接干。

穷举所有n可能被拆解的可能性，看哪种拆分的乘积最大。

n可以被拆解为j和n - j两个正整数，穷举所有的j，看哪个j * (n - j)最大就选哪个j，1 <= j <= n - 1。

题目说至少是拆分两个，还可以继续拆分，所以可以对n - j继续拆分，也可以不继续拆分。
n - j继续拆解，就划分为子问题了。

暴力递归拆解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    fun integerBreak(n: Int): Int {
        if (n == 0 || n == 1) return 0
        if (n == 2) return 1
        var maxProduct = -1
        for (j in 1 until n) {
            val i = n - j
            maxProduct = maxOf(
                maxProduct,
                j * i,
                j * integerBreak(i)
            )
        }
        return maxProduct
    }
}

记忆化递归
存在很多重叠子问题，计算量过大，时间复杂度指数级别，需要记录中间计算结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    fun integerBreak(n: Int): Int {
        val memo = IntArray(n + 1) { 0 }
        fun select(n: Int): Int {
            if (n == 0 || n == 1) return 0
            if (n == 2) return 1
            if (memo[n] != 0) return memo[n]
            var maxProduct = -1
            for (j in 1 until n) {
                val i = n - j
                maxProduct = maxOf(
                    maxProduct,
                    j * i,
                    j * integerBreak(i)
                )
            }
            memo[n] = maxProduct
            return maxProduct
        }
        return select(n)
    }
}

自底向上递推

设dp[i]为i拆解为多个正整数后的最大乘积。
先求出小的dp[i]再求大的；每个dp[i]穷举所有拆解情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    fun integerBreak(n: Int): Int {
        val dp = IntArray(n + 1) { 0 }
        dp[2] = 1
        for (i in 2..n) {
            for (j in 1 until i) {
                dp[i] = maxOf(
                    dp[i],
                    j * (i - j),
                    j * dp[i - j]
                )
            }
        }
        return dp[n]
    }
}