重庆渝云建设有限公司官方网站,网页版qq音乐登录入口,天津做网站排名,wordpress如何更换主机1. 题目
给定一个正整数 n#xff0c;将其拆分为至少两个正整数的和#xff0c;并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 1 1, 1 1 1。示例 2:
输入: 10
输出: 36
解释: 10 3 3 4, 3 3 4 36。
说明: 你可以假设 …1. 题目
给定一个正整数 n将其拆分为至少两个正整数的和并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2
输出: 1
解释: 2 1 1, 1 × 1 1。示例 2:
输入: 10
输出: 36
解释: 10 3 3 4, 3 × 3 × 4 36。
说明: 你可以假设 n 不小于 2 且不大于 58。《剑指offer》同题 面试题14- I. 剪绳子
来源力扣LeetCode 链接https://leetcode-cn.com/problems/integer-break 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
dp[n]dp[n]dp[n] 表示获得的最大乘积当 n1 时可以拆成 (1,n),(2,n−1),(3,n−2),…,(n,1)(1,n),(2,n-1),(3,n-2),…,(n,1)(1,n),(2,n−1),(3,n−2),…,(n,1)dp[n1]max(1∗dp[n],2∗dp[n−1],...,n∗dp[1],...1∗n,2∗(n−1),...,n∗1)dp[n1]max(1*dp[n],2*dp[n-1],...,n*dp[1],...1*n,2*(n-1),...,n*1)dp[n1]max(1∗dp[n],2∗dp[n−1],...,n∗dp[1],...1∗n,2∗(n−1),...,n∗1)
class Solution {
public:int integerBreak(int n) {int dp[n1] {0};dp[2] 1;int i, j;for(i 3; i n; i){for(j 1; j i-2; j)dp[i] max(dp[i], max(j*dp[i-j], j*(i-j)));}return dp[n];}
};class Solution {
public:int cuttingRope(int n) {int dp[n1] {0};dp[2] 1;int i, j;for(i 3; i n; i){ for(j 1; j i; j)dp[i] max(dp[i], max(j,dp[j])*max(i-j, dp[i-j]));}return dp[n];}
};n 很大的时候避免溢出《剑指offer》面试题14- II. 剪绳子 II
有结论划分成尽可能多的3最多2个2
求余12个2求余21个2
class Solution {
public:int cuttingRope(int n) {if(n 3)return n-1;//尽可能多的3, 两端最多只有2个2int p n/3, q n%3;long long sum 1;if(q 1)//多分出3个凑成4 变成2*2 3*1sum * 4, p - 1;if(q 2) sum * 2;for(int i 0; i p; i){sum sum * 3 % 1000000007;}return sum;}
};
