LeetCode <dp>343. Integer Break

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];
    }

总结:

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

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

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

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程

Python数据类型之字符串第四季

各位小伙伴们 “黑一”快乐 本节课非常非常重要 请各位小伙伴 一定认真理解和学习 技术要点: 内建函数 函数的理解 如何使用一个函数 capitalize()函...

1840
来自专栏女程序员的日常

虚函数&多态

对于经常被问到的虚函数和多态的问题,发现百度百科回答得十分详细,所以自己在百度百科上的解释进行总结 一、虚函数 (1)虚函数简介:在某基类中声明为virtua...

2321
来自专栏vue学习

函数声明提升与变量提升

1.当在函数的作用域里定义一个和外部变量一样的名称的变量时,变量声明会提升至第一句,但是赋值则不变

1012
来自专栏工科狗和生物喵

【计算机本科补全计划】《C++ Primer》:类型转换

正文之前 学习,不如爆文?反正晚上也不会学习,某个家伙也对我爱理不理的!!!!(这才是最骚的吧),刚好欠了 C++ Primer太多烂账了。不如赶紧还了! 对了...

3098
来自专栏诸葛青云的专栏

C语言夺命题十例,为啥C语言的总是这么恶趣味?

这些问题测试了C语言的高级知识,包括一些很少使用的特性。有效的C编程需要对诸如未定义的行为,递归和指针算术等概念有深入的理解,但是这些故意复杂的例子并不代表现实...

2003
来自专栏AzMark

Python字符串

1555
来自专栏编程

详解 Python的enumerate 函数

你应该在何时何地,如何使用内置的 enumerate() 函数来写出更加简洁、更加具有 Python 范儿的循环结构呢? ? Python 的 enumerat...

2257
来自专栏编码前线

关于三种工厂模式的总结

工厂模式分为简单工厂模式,工厂方法模式和抽象工厂模式,它们都属于设计模式中的创建型模式。其主要功能都是帮助我们把对象的实例化部分抽取了出来,目的是降低系统中代...

1071
来自专栏程序员互动联盟

【编程基础】C++ Primer快速入门五:实用的模板库

除上篇博客介绍的基本数据类型外,C++ 还定义了一个内容丰富的抽象数据类 型标准库。包括 string 和 vector,它们分别定义了字符串和矢量(集合)。s...

2935
来自专栏云霄雨霁

设计模式----工厂方法模式

1440

扫码关注云+社区

领取腾讯云代金券