前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode <dp>343. Integer Break

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:

代码语言:javascript
复制
Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

代码语言:javascript
复制
Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

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

解法一:

最为暴力的解法:

代码语言:javascript
复制
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;
}

解法二:

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

代码语言:javascript
复制
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;
}

注意:这里的:

代码语言:javascript
复制
   int res = 0;

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

解法三:

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

代码语言:javascript
复制
    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];
    }

总结:

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

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

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 343.Integer Break
    • 解法一:
    • 解法二:
      • 解法三:
        • 总结:
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档