美文网首页
343. Integer Break

343. Integer Break

作者: HalcyonMoon | 来源:发表于2016-06-29 23:14 被阅读0次

    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.

    public class Solution {
        public int integerBreak(int n) {
            int dp[]= new int[n>6?n+1:7];
            dp[0] = 0;
            dp[1] = 1;
            dp[2] = 1;
            dp[3] = 2;
            dp[4] = 4;
            dp[5] = 6;
            dp[6] = 9;
            for (int i = 7; i <= n; i++) {
                dp[i] = 3 * dp[i - 3];
            }
            return dp[n];
        }
    }
    

    相关文章

      网友评论

          本文标题:343. Integer Break

          本文链接:https://www.haomeiwen.com/subject/wcyxjttx.html