[leetcode]343. Integer Break

[leetcode]343. Integer Break

题目链接：/

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume that n is not less than 2 and not larger than 58.

 一、动态规划

  dp[n]为对应n的最大积，

  dp[1]=1,dp[2]=1

  dp[n]=max(j*dp[n-j],max(dp[n],j*(n-j)))

class Solution {
public:int integerBreak(int n) {int dp[n+1];dp[1]=1;dp[2]=1;
for(int i=3;i<=n;i++){dp[i]=-1;for(int j=1;j<i;j++){dp[i]=max(j*dp[i-j],max(dp[i],(j*(i-j))));}}return dp[n];}
};

二、数学推导

  易知，把n拆分成几个相等的数时它们的积最大

 假设可以把n拆分成实数，设每一个数为x,则一共有n/x个数。

 设它们的积为f(x),则f(x)=x^(n/x)，那么怎么求f(x)最大值呢？求导数！

 f′(x)=(n/x²)  *  x^(n/x)  * (1-lnx)

 当x=e时取极大值；而我们题目里规定x为整数，那么我们只需要取的x越靠近e越好。那么2<e<3，而且e=，所以取3是最好的，如果取不到3就取2。

class Solution {
public:int integerBreak(int n) {if(n == 2)return 1;else if(n == 3)return 2;else if(n%3 == 0)return pow(3, n/3);else if(n%3 == 1)return 2 * 2 * pow(3, (n - 4) / 3);else return 2 * pow(3, n/3);}
};