整数划分--思考问题背后的数学原理

内容简介：今天在 leetcode 做动态规划的题, 做到一道整数划分的题目如下这个用动态规划很容易写出代码如下,后来想到, 这不就是均值不等式吗? 给定和, 求积最大, 即

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

class Solution:
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.dic={1:1}
        for i in range(2,n+1):
            mx = 1
            for j in range(1,i):
                prod = j*self.dic[i-j]
                mx =max(mx,prod,j*(i-j))
            self.dic[i] = mx
        return self.dic[n]

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n<5:
            return [0, 0, 1, 2, 4][n]
        x = n % 3
        if x == 0:
            return 3 ** (n // 3)
        if x == 1:
            return 3 ** (n // 3 - 1) * 4
        return 3 ** (n // 3) * 2

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网

关注我们，获取更多IT资讯^_^

查看所有标签

• 如何划分限界上下文
• 如何给 Hadoop 集群划分角色
• 【LeetCode】贪心算法--划分字母区间（763）
• JVM笔记-运行时内存区域划分
• Python列表推导式一则：等价类划分
• 简单解决大型 Flask 蓝图的路由划分

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。