leetcode343-整数拆分

原题

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

示例 1:

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

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

说明: 你可以假设 n 不小于 2 且不大于 58。

解法

思想

我感觉我写的动态规划还挺暴力的。。。没看懂别人的动态规划,我看别人就两三行写完了QAQ
我确实8太行

代码

class Solution {
    Integer[][] matrix;
    public int integerBreak(int n) {
        int max = 0;
        matrix = new Integer[n+1][n+1];
        int cache;
        for(int i = 2;i<=n;i++){
            if((cache = maxMult(n,i)) > max) max = cache;
        }
        return max;
    }
    public int maxMult(int num,int n){
        if(n == 1) return num;
        if(n == 2){
            return (num/2)*((num+1)/2);
        }else{
            if(matrix[num][n]!=null) return matrix[num][n];
            int max = 0;
            for(int i = n-1;i<num;i++){
                int cache;
                if((cache = maxMult(i,n-1)*(num-i)) > max) max = cache;
            }
            matrix[num][n] = max;
            return max;
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode343-%e6%95%b4%e6%95%b0%e6%8b%86%e5%88%86/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年4月12日 16:20
下一篇 2020年4月13日

相关推荐

  • 剑指offer13-机器人的运动范围

    原题(来源Leetcode) 地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下…

    算法 2020年4月8日
    0110
  • leetcode153-寻找旋转排序数组中的最小值

    原题 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值,…

    算法 2020年1月3日
    080
  • leetcode145-二叉树的后序遍历

    原题 给定一个二叉树,返回它的 后序 遍历。 示例: 输入: [1,null,2,3]  1   \    2 &nbs…

    算法 2020年1月10日
    080
  • leetcode509-斐波那契数

    原题 斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0,   F(1) …

    算法 2020年1月21日
    0120
  • leetcode1371-每个元音包含偶数次的最长子字符串

    原题 给你一个字符串 s ,请你返回满足以下条件的最长子字符串的长度:每个元音字母,即 'a','e','i','o','u' ,在子字符串中都恰好出现了偶数次。 示例 1: 输入…

    算法 2020年5月20日
    01560
  • leetcode2-两数相加

    原题 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回…

    算法 2019年12月17日
    080
  • leetcode17-电话号码的字母组合

    原题 给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。 给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。 示例: 输入: "23" 输出: …

    2020年5月3日
    0130
  • leetcode123-买卖股票的最佳时机III

    原题 给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。 注意: 你不能同时参与多笔交易(你…

    算法 2020年6月16日
    01540
  • leetcode456-132模式

    原题 给定一个整数序列:a1, a2, ..., an,一个132模式的子序列 ai, aj, ak 被定义为:当 i < j < k 时,ai < ak &lt…

    算法 2020年1月30日
    0150
  • leetcode75-颜色分类

    原题 给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 此题中,我们使用整数 0、 1 和 2 分…

    算法 2020年4月19日
    0230

发表回复

登录后才能评论