万维网络(临沂网站建设),抖音小程序游戏怎么免广告拿奖励,民治营销型网站,学生求职网站的需求分析怎么做题目来源#xff1a;https://leetcode.cn/problems/integer-break/description/ C题解1#xff1a;动态规划。dp[i] 代表数字i拆分后得到的最大乘积。递归公式为拆分后两个数的最大乘积相乘#xff0c;即 dp[i] max(dp[i], dp[j] * dp[i-j])。对于n2或3需要另外讨论。
cla…题目来源https://leetcode.cn/problems/integer-break/description/ C题解1动态规划。dp[i] 代表数字i拆分后得到的最大乘积。递归公式为拆分后两个数的最大乘积相乘即 dp[i] max(dp[i], dp[j] * dp[i-j])。对于n2或3需要另外讨论。
class Solution {
public:int integerBreak(int n) {if(n 2) return 1;else if(n 3) return 2;vectorint dp(n1, 0);dp[1] 1;dp[2] 2;dp[3] 3;for(int i 2; i n; i) {for(int j 1; j i; j){dp[i] max(dp[i], dp[j] * dp[i-j]);}}return dp[n];}
};
C题解2来源代码随想录动规五部曲。
确定dp数组dp table以及下标的含义。dp[i]分拆数字i可以得到的最大乘积为dp[i]。确定递推公式。 dp[i]最大乘积是怎么得到的呢其实可以从1遍历j然后有两种渠道得到dp[i]。一个是j * (i - j) 直接相乘另一个是j * dp[i - j]相当于是拆分(i - j)对这个拆分不理解的话可以回想dp数组的定义。那有同学问了j怎么就不拆分呢j是从1开始遍历拆分j的情况在遍历j的过程中其实都计算过了。那么从1遍历j比较(i - j) * j和dp[i - j] * j 取最大的。递推公式dp[i] max(dp[i], max((i - j) * j, dp[i - j] * j))也可以这么理解j * (i - j) 是单纯的把整数拆分为两个数相乘而j * dp[i - j]是拆分成两个以及两个以上的个数相乘。dp的初始化。初始化dp[2] 1。确定遍历顺序。先来看看递归公式dp[i] max(dp[i], max((i - j) * j, dp[i - j] * j))。dp[i] 是依靠 dp[i - j]的状态所以遍历i一定是从前向后遍历先有dp[i - j]再有dp[i]。举例推导dp数组
class Solution {
public:int integerBreak(int n) {vectorint dp(n 1);dp[2] 1;for (int i 3; i n ; i) {for (int j 1; j i / 2; j) {dp[i] max(dp[i], max((i - j) * j, dp[i - j] * j));}}return dp[n];}
};
C题解3来源代码随想录贪心算法。“拆分一个数n 使之乘积最大那么一定是拆分成m个近似相同的子数相乘才是最大的”。每次拆成n个3如果剩下是4则保留4然后相乘但是这个结论需要数学证明其合理性
class Solution {
public:int integerBreak(int n) {if (n 2) return 1;if (n 3) return 2;if (n 4) return 4;int result 1;while (n 4) {result * 3;n - 3;}result * n;return result;}
};
