資訊專欄INFORMATION COLUMN
摘要：思路動(dòng)態(tài)規(guī)劃，前五個(gè)數(shù)的最大乘積為，后面的第個(gè)數(shù)的最大乘積，由從后往前數(shù)包括本身的第三個(gè)數(shù)乘以得到。何睿何睿前個(gè)數(shù)的最大乘積動(dòng)態(tài)規(guī)劃第個(gè)數(shù)的最大乘積為往前數(shù)第三個(gè)數(shù)思路與上面的思路一致，優(yōu)化了空間源代碼文件在這里。
Description
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.
Note: You may assume that n is not less than 2 and not larger than 58.
給定一個(gè)正整數(shù) n，將其拆分為至少兩個(gè)正整數(shù)的和，并使這些整數(shù)的乘積最大化。 返回你可以獲得的最大乘積。
示例 1:
輸入: 2
輸出: 1
解釋: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
輸入: 10
輸出: 36
解釋: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
說(shuō)明: 你可以假設(shè) n 不小于 2 且不大于 58。
動(dòng)態(tài)規(guī)劃，前五個(gè)數(shù)的最大乘積為 1, 2, 4, 6, 9，后面的第 i 個(gè)數(shù)的最大乘積，由從后往前數(shù)（包括 i 本身）的第三個(gè)數(shù)乘以 3 得到。
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-04-08 17:35:39
# @Last Modified by: 何睿
# @Last Modified time: 2019-04-08 18:15:43
class Solution:
def integerBreak(self, n: int) -> int:
# 前 5 個(gè)數(shù)的最大乘積
tmp = [1, 2, 4, 6, 9]
for i in range(5, n - 1):
# 動(dòng)態(tài)規(guī)劃：第 i 個(gè)數(shù) 的最大乘積為 3 * 往前數(shù)第三個(gè)數(shù)
tmp.append(3 * tmp[i - 3])
return tmp[n - 2]
def integerBreak2(self, n: int) -> int:
# 思路與上面的思路一致，優(yōu)化了空間
if n == 2: return 1
if n == 3: return 2
tmp = [4, 6, 9]
for i in range(n - 6):
tmp[i % 3] *= 3
return tmp[(n - 1) % 3]
源代碼文件在 這里 。
?本文首發(fā)于 何睿的博客 ，歡迎轉(zhuǎn)載，轉(zhuǎn)載需保留 文章來(lái)源 ，作者信息和本聲明.
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/43560.html
摘要：題目要求將一個(gè)正整數(shù)分解為兩個(gè)或兩個(gè)以上的正整數(shù)，要求這些正整數(shù)的乘積最大。思路和代碼這里應(yīng)用了一個(gè)數(shù)學(xué)的思路。假設(shè)我們有一個(gè)數(shù)字，該數(shù)組可以隨機(jī)分解為和。因此取時(shí)可以得到最好的結(jié)果。至于為什么我們需要盡可能用分解，因?yàn)椤? 題目要求 Given a positive integer n, break it into the sum of at least two positive in...
Problem 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. For example, given n = 2...
Problem A website domain like discuss.leetcode.com consists of various subdomains. At the top level, we have com, at the next level, we have leetcode.com, and at the lowest level, discuss.leetcode.com...
摘要：棧法復(fù)雜度時(shí)間空間思路逆波蘭表達(dá)式的計(jì)算十分方便，對(duì)于運(yùn)算符，其運(yùn)算的兩個(gè)數(shù)就是這個(gè)運(yùn)算符前面的兩個(gè)數(shù)。注意對(duì)于減法，先彈出的是減號(hào)后面的數(shù)。 Evaluate Reverse Polish Notation Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operato...
Problem Implement function atoi to convert a string to an integer. If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values...
閱讀 2409·2021-11-23 09:51
閱讀 1243·2021-11-22 13:52
閱讀 3676·2021-11-10 11:35
閱讀 1307·2021-10-25 09:47
閱讀 3078·2021-09-07 09:58
閱讀 1123·2019-08-30 15:54
閱讀 2888·2019-08-29 14:21
閱讀 3097·2019-08-29 12:20
