LeetCode <dp>343. Integer Break

原创

大学里的混子

修改于 2019-03-07 17:29:11

4580

修改于 2019-03-07 17:29:11

文章被收录于专栏：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.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

题目大意：将一个数分为几个数相加之和，求这几个数的最大乘积。

解法一：

最为暴力的解法：

public static int IntegerBreak(int n){
    if (n == 1) return n;
    if (n == 2) return 1;
    int res = 0;
    for (int i = 1; i < n - 1; i++){
        res = Math.max(i * (n-i),Math.max(res,i * IntegerBreak(n-i)));
    }
    return res;
}

解法二：

这是一个典型的动态规划问题。首先采用记忆化搜索的方式。

public int integerBreak(int n) {
    int[] memo = new int[n+1];
    return breakInteger(n,memo);
}

public int breakInteger(int n, int[] memo ){
    if (n == 1) return 1;
    if (memo[n]!=0) return memo[n];
    int res = 0;
    for (int i = 1;i<n;i++){
         res = Math.max(Math.max(res,i*breakInteger(n-i,memo)),i*(n-i));
    }
    memo[n] = res;
    return res;
}

注意：这里的：

   int res = 0;

写在函数的里面和函数的外面都是可以的，写在函数的外面可能容易理解点，写在里面要注意这里递归程序每次都会定义res，所以res并不是一个变量。

解法三：

本解法采用的是动态规划的解法。

    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[1] = 1;
        for (int i=2;i<=n;i++){
            //求解memo[i]
             for (int j=1;j<i;j++){
                 // j+(i-j)
                   dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
             }
        }
        return dp[n];
    }

总结：

记忆化搜索是利用一个记录状态的数组配合递归来解决问题，思路是自顶向下。
动态规划的思路是自底向上的解法。
前者是先假设子问题已经解决，后者是先解决子问题再解决再解决后续问题。

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

编程算法

登录后参与评论

0 条评论

热度