|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 糖逗 于 2020-4-29 15:07 编辑
题目描述:
- 给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
- 示例 1:
- 输入: 2
- 输出: 1
- 解释: 2 = 1 + 1, 1 × 1 = 1。
- 示例 2:
- 输入: 10
- 输出: 36
- 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
- 说明: 你可以假设 n 不小于 2 且不大于 58。
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/integer-break
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int solution(int n) {
- if(n <= 3) 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[i-j]*dp[j]);
- }
- }
- return dp[n];
- }
- int main(void){
- int input;
- cin >> input;
- cout << solution(input) << endl;
- return 0;
- }
复制代码 |
|