【leetCode-DP】343. 整数拆分

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

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

通过列举出一些数后可以发现最大乘积都是和2或者3相关（其中4也是由2 组成），因此一个数优先使用3，不能的话用2去匹配

同时注意输入数据为4以下的情况。

code:

非DP:

    public static int power (int N,int num) {
        int rs = 1;
        for(int i = 0;i < num; i++) {
            rs *= N;
        }
        return rs;
    }
    public static int integerBreak(int n) {
        if(n < 4){
            return n-1;
        }
        int m = n % 3;
        if (m == 0) {
            return power(3 ,n/3);
        } else if(m == 1) {
            return power(3,n/3-1) * 4;
        } else {
            //m == 2
            return power(3,n/3) * 2;
        }
    }

DP:

通过前面列出的数字规律可以看出dp[i] = dp[i-3] * 3

版权声明：本文来源CSDN，感谢博主原创文章，遵循 CC 4.0 by-sa 版权协议，转载请附上原文出处链接和本声明。
原文链接：https://blog.csdn.net/grit_icpc/article/details/103720868
站方申明：本站部分内容来自社区用户分享，若涉及侵权，请联系站方删除。

发表于 2020-03-06 22:48:07
阅读 ( 1069 )
分类：算法

【leetCode-DP】343. 整数拆分

你可能感兴趣的文章

精选的优质文章

0 条评论

官方社群

GO教程

推荐文章

猜你喜欢

随便看看