C++ 0ms DP solution with explanation in Chinese


  • 7
    T
    /*
     * 从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.


  • 1
    A

    My translation, please check, thx for your solution BTW

    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];
        }
    };

Log in to reply
 

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