Cut rope / integer split

When i > 2 when , Let's say we have a positive integer i When the first positive integer is split j（1<=j<i - 1, Because from 2 Start ） Then there are two options ：

• take i Split into j and i-j And , And i-j Cannot be split into multiple positive integers , The product at this point is j*（i-j）
• take i Split into j and （i-j） And , And i-j You can continue to split into multiple positive integers , The achievement at this time is j*dp[i-j]
• dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j)); Just take dp[i] The maximum of

class Solution {
    
public:
    int integerBreak(int n) {
    
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
    
            for (int j = 1; j < i - 1; j++) {
    
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};