阿里云的网站空间,中国临海建设规划局网站,厦门seo排名,公司网站建设费属于什么费用LeetCode 343. 整数拆分 思路#xff1a;
通过题目我们可以知道#xff0c;一个正整数最少拆成2个数#xff0c;最多拆成n个数#xff0c;即可拆分的个数为2#xff5e;n
若将拆除的第一个正整数令为k#xff0c;那么剩下的数则为n-k#xff0c;此时可以不拆分#x…LeetCode 343. 整数拆分 思路
通过题目我们可以知道一个正整数最少拆成2个数最多拆成n个数即可拆分的个数为2n
若将拆除的第一个正整数令为k那么剩下的数则为n-k此时可以不拆分也可以继续拆成2n-k个若我们可以计算出n-k拆分后的最大乘积则在此基础上很容易得出n拆分后的最大乘积。此时容易想到使用动态规划的思想通过不断求解子问题的最优解来确定原问题的最优解
那么我们令dp[i]为正整数i拆分后的最大乘积最少拆成2个最多拆成i个
dp[0]dp[1]无意义不必初始化则初始化dp[2]1
此时可以将i从3开始遍历到n来计算每个正整数拆分后的最大乘积dp[i] 在每个数i的遍历过程中可以将i先拆分出j则剩下的为i-j则有
dp[i]max(dp[i],max(dp[i-j]*j,(i-j)*j))即可以将i只拆分成j和i-j两个数此时乘积为i*(i-j) 也可以将i先拆分成j剩下的i-j继续拆分此时乘积为j*dp[i-j] 取其中的最大乘积即为dp[i]
最后dp[n]即为n拆分后所有数的最大乘积
代码
#includestdio.h
#includevector
#includestring.h
#includealgorithm
using namespace std;class Solution {
public:int integerBreak(int n) {int dp[60];memset(dp, 0, sizeof(dp));dp[2]1;for(int i3;in;i)for(int j1;ji;j)dp[i]max(dp[i],max(dp[i-j]*j,(i-j)*j));return dp[n];}
};int main()
{int target 10;Solution *solution new Solution();int anssolution-integerBreak(target);printf(%d\n,ans);free(solution);return 0;
}总结 做这道题时没有想清楚dp[i]的定义错误地认为dp[i]就是最大乘积不论何种情况是拆分还是没拆分所以写成了dp[i]max(dp[i],dp[i-j]*j)没有想清楚dp[i]是拆分后的最大乘积即这个代码表示的是拆分成3个或者更多个数后的最大乘积把dp[i]拆分为两个数的情况给 遗漏了。。。 参考链接https://blog.csdn.net/zhizhengguan/article/details/124453544
