您的浏览器不支持CSS3,建议使用Firfox、Chrome等浏览器,以取得最佳显示效果

LeetCode:整数拆分问题

开发技术 162℃ 0 2个月前 (04-04)

摘要

LeetCode:整数拆分问题

343. 整数拆分

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

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

这里比较容易出错的是,必须拆分为至少2个正数,而不能不拆分。

动态规划的解法1

先证明一个结论:数字s拆分为两数之和,两数越接近,乘积越大(或者可以说是,周长相同的矩形,越接近正方形,面积越大)。

a + b = s
设 a = s/2 + p, b = s/2 - p
有 a * b = (s/2+p)(s/2-p) = (1/4)s^2 - p^2
因此 abs(p)越小时,a、b越接近,a*b越大

定义 f(n) 为数字n可以拆分至少2个得到的最大乘积:

  • 拆分为2个时,最大的乘积是(n/2) * (n - n/2)。如果n为偶数,两者相等,如果n为奇数,两者相差1。
  • 拆分为2个以上,第一个数字选 i 时( 0 < i < n ),最大乘积为 i * f(n-i)

因此:

  • f(n) = max { (n/2)*(n-n/2), 1*f(n-1), ..., (n-1)*f(1) }

初值:

  • f(1) = 0
  • f(2) = 1 (1 + 1)
  • f(3) = 2 (1 + 2)

于是动态规划解法为:

class Solution {
    public int integerBreak(int n) {
        if (n <= 3) return n-1;
        // dp表示拆分为至少2个得到的最大乘积
        int[] dp = new int[n+1];
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 2;
        for (int i = 4; i <= n; ++i) {
            dp[i] = i/2 * (i - i/2);
            for (int j = 1; j < i; ++j) {
                dp[i] = Math.max(dp[i], j * dp[i-j]);
            }
        }
        return dp[n];
    }
}

动态规划的解法2

证明一个结论:当整数s >= 4时,s拆分为至少2个数字的最大乘积,一定大于等于s(即不拆分)。

设 s = p + q,且p,q均为正整数

求解
pq >= p + q
pq - p - q >= 0
pq - p - q + 1 >= 1
(p-1)(q-1) >= 1

由于 p-1, q-1 均为自然数,因此
p >= 2, q >= 2

于是
s = p + q >= 4

所以当s>=4时,拆分为两个数一定大于等于不拆分
进一步,这两个数还可能继续拆分,使乘积更大

定义 f(n) 为数字n拆分得到的最大乘积,而g(n) 为数字n拆分或不拆分得到的最大乘积:

  • g(n) = max { n, 1*g(n-1), ... (n-1)*g(1) }

n >= 4 时,必须要拆分才能得到最大值(等于4时可拆可不拆),因此上式max中的第一项n可以省去,且f(n) = g(n),于是:

  • f(n) = g(n) = max { 1*g(n-1), ..., (n-1)*g(1) }

最后使用动态规划实现如下:

class Solution {
    public int integerBreak(int n) {
        if (n <= 3) return n-1;
        // dp表示拆分或不拆分得到的最大乘积
        // 1 <= n <= 3, dp[n] = g(n)
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        // n>=4, dp[n] = f(n) = g(n)
        for (int i = 4; i <= n; ++i) {
            for (int j = 1; j < i; ++j) {
                dp[i] = Math.max(dp[i], j * dp[i-j]);
            }
        }
        return dp[n];
    }
}

数学解法

这道题也可以用纯数学解法,性能更好,可参考 题解

最后,欢迎扫码关注微信公众号。微软 / Shopee / Coupang / BAT等国内外企业内推、行业和技术交流,也可以加我微信 jzj2015(注明来自博客),拉你进技术群。

本文由原创,转载请注明来源:https://www.paincker.com/leetcode-integer-break
(标注了原文链接的文章除外)

0

暂无评论

评论前:需填写以下信息,或 登录

用户登录

忘记密码?