# C++ 0ms DP solution with explanation in Chinese

• ``````/*
* 从n = 2开始递推，递推到n = 4的时候，4可以拆分成1和3或2和2
* 那么3要不要继续拆分呢？2要不要继续拆分呢？
* 不需要。因为我们已经把拆分2或3能得到的最大值分别计算好存在dp[2]和dp[3]了
* 所以我们只需要比较2和dp[2]、3和dp[3]谁更大就知道要不要继续拆分
* 所以对每个n，我们只需要考虑拆分成两个数a b的情况，然后看比较a和dp[a]
* 以及b和dp[b]谁大就用谁相乘，如果dp[a]>a，表示dp[a]继续拆分能得到比不拆分
* 更大的值，那么就拆分a，对于dp[b]和b也一样
*/
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1, 0);
for(int i = 2; i <= n; i++) {
for(int j = 1; j <= i / 2; j++) {
dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));
}
}
return dp[n];
}
};
``````

At most of the time I learnt from others post, this time let me share. Since I haven't seen any dp solution with detailed explanation, I write this post for your reference.

I don't know how to make this explanation clear in English. Hope anyone with a better command of English can translate it for others. THanks.

``````class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n+1, 0); // Initialize the result vector, dp[n] is the max product of n's splits
for (int i=2;i<=n;i++) {
int dp_i_max = INT_MIN;
for (int j=1;j<=(i/2);j++) {
dp[i] = max(i-j,dp[i-j])*max(j,dp[j]); // We only need to consider situations where i is splited into 2 parts, because we can decide whether to use their original form (part_1/2) or product of splited parts (dp[part_1/2]) by comparing these 2 pairs (further split results have been considered before current i)
if (dp_i_max < dp[i]) // Check current max value to see if we need to update it to be dp[i]
dp_i_max = dp[i];
}
dp[i] = dp_i_max; // Save the max value in dp[i]
}
return dp[n];
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.