LeetCode343.Integer Break

题意

给一个n(2≤n≤58),求相加等于n且乘积最大的一组整数的积。

思路

A. DP解法(O(N))

dp[i]维护数字i拆分后最大的积，由于有些数字不拆分比拆分后的积大，例如3
所以状态转移方程为 dp[i] = max{ max(dp[i-k],i-k) * max(dp[k],k) }(1≤k<i)

B. 数学解法(O(logN))

  1. 平方平均数:

  3. 算术平均数:

  4. 几何平均数:

  5. 调和平均数:

调和平均数 ≤ 几何平均数 ≤ 算术平均数 ≤ 平方平均数

所以把n拆分成几个相等的数时它们的积最大。
假设每一个数为x,则一共有n/x个数。
他们的积f(x) = xn/x,现在问题变为x为何值时，函数取得最大值。求导！
f’(x) = (n/x2) x(n/x) (1-lnx),得x为e时，取得极大值。
e = 2.71828…,所以取3时，所得的积最大。

代码

A

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

B

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public int integerBreak(int n) {
        if(n==2) return 1;
        if(n==3) return 2;
        int product = 1;
        while(n>4){
            product*=3;
            n-=3;
        }
        product*=n;  
        return product;
    }
}

留言

2017-02-04
⬆︎TOP