We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
输入: 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。
输入: 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
说明: 你可以假设 n 不小于 2 且不大于 58。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/integer-break
The text was updated successfully, but these errors were encountered:
可以多次拆分,求最大值,可以使用动态规划。 设置一个数组dp,0和1是无法再被拆分的,所以dp[0]和dp[1]都是0,然后我们假设n拆分出来的一个正整数是k,那么剩下的就是n-k,现在就有两种情况了:
dp[n] = k * n-k
dp[n] = k * dp[n-k]
dp[n] = max(k * (n-k), k * dp[n-k])
func integerBreak(n int) int { dp := make(map[int]int, n) dp[0] = 0 dp[1] = 0 for i := 2; i <= n; i++ { v := 0 for j := 1; j < i; j++ { v = max(v, max(j*(i-j), j*dp[i-j])) } dp[i] = v } return dp[n] } func max(x, y int) int { if x > y { return x } return y }
Sorry, something went wrong.
No branches or pull requests
给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
示例 2:
说明: 你可以假设 n 不小于 2 且不大于 58。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/integer-break
The text was updated successfully, but these errors were encountered: