leetcode 343 Integer Break C++

2017-01-03 19:13:42来源:CSDN作者:a2331046人点击

第七城市

这道题就是个证明题,证明分解为3的时候最大,不足的地方用2补充。

在不知道是3的情况下证明还是挺复杂的,用到了挺多高数的知识,如果只是证明3最好还是比较容易的,这里就不说了。

代码如下:

    int integerBreak(int n) {        if (n == 2) return 1;        if (n == 3) return 2;                int result = 1;        int num = n / 3;        int remainNum = n % 3;        if (remainNum == 1) num--;                for (int i = 0;i<num;i++) {            result *= 3;        }                if (remainNum == 1) result *= 4;        else if (remainNum == 2) result *= 2;                return result;    }

当然还有dp的解法,O(n)。用dp[i]代表数字为i的时候乘积的最大值。求出所有的dp[i]的时候,遍历一遍所有的dp[n-i]*dp[i]的乘积,看哪个最大即可。

第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台