专栏首页木又AI帮【leetcode刷题】T167-整数拆分

【leetcode刷题】T167-整数拆分

木又连续日更第3天(3/100)


木又的第167篇leetcode解题报告

动态规划类型第12篇解题报告

leetcode第343题:整数拆分

https://leetcode-cn.com/problems/integer-break/


【题目】

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

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

示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。

【思路】

对于所有的j<i,dp[i] = max(dp[i], dp[j] * dp[i-j])

【代码】

python版本

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 4:
            return n-1
        dp = [i for i in range(n+1)]
        for i in range(4, n+1):
            for j in range(1, i//2 + 1):
                dp[i] = max(dp[i], dp[j] * dp[i-j])
        return dp[-1]

C++版本

class Solution {
public:
    int integerBreak(int n) {
        if(n < 4)
            return n-1;
        vector<int> dp(n+1, 0);
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i=4; i < n+1; i++){
            for(int j=1; j <= i/2; j++){
                dp[i] = max(dp[i], dp[j] * dp[i-j]);
            }
        }
        return dp.back();
    }
};

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 打卡群刷题总结0801——解码方法

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 打卡群刷题总结0718——最小路径和

    链接:https://leetcode-cn.com/problems/minimum-path-sum

    木又AI帮
  • 【leetcode刷题】T168-计算各个位数不同的数字个数

    https://leetcode-cn.com/problems/count-numbers-with-unique-digits/

    木又AI帮
  • LeetCode 123. 买卖股票的最佳时机 III(动态规划)

    Michael阿明
  • 不同的二叉搜索树

    对于二叉树问题的一般解决思路为将该树分为根结点,左子树,右子树,然后再对左右子树各个击破,最终将信息返回到根结点。

    你的益达
  • [Leetcode][python]Distinct Subsequences/不同子序列

    同样你可以打印出dp看结构:上半区都为0,因为不可能,dp[0][0]为1因为空转空有一种可能(不删除)

    后端技术漫谈
  • 打卡群刷题总结0801——解码方法

    PS:刷了打卡群的题,再刷另一道题,并且总结,确实耗费很多时间。如果时间不够,以后的更新会总结打卡群的题。

    木又AI帮
  • 巧解动态规划问题

    前言:最近在力扣刷题,但是之前从没有接触过算法题,有的看答案都看不懂,后来做的题做多了发现有好多类似的题目,所以我打算总结一下规律。

    wsuo
  • LeetCode 357. 计算各个位数不同的数字个数(DP)

    给定一个非负整数 n,计算各位数字都不同的数字 x 的个数,其中 0 ≤ x < 10n。

    Michael阿明
  • HDU-4405-Aeroplane chess

    ACM模版 描述 ? 题解 概率 DPDP,求期望。 状态转移方程很容易想,设 dp[i]dp[i] 表示在位置 ii 还需要多少期望才能到达终点,那么 dp[...

    f_zyj

扫码关注云+社区

领取腾讯云代金券