Super easy C++ DP solution


  • 0
    F
    static vector<int> dp;
    class Solution {
    public:
        int integerBreak(int n) {
            if (dp.empty()) {
                dp.push_back(0);
                dp.push_back(1);
            }
            if (dp.size() >= n) return dp[n-1];
            for (int i = dp.size(); i < n; i ++) {
                int cur = 0;
                for (int k = i - 1; k > 0; k--) {
                    cur = max(cur, max(k, dp[k - 1]) * max(i - k + 1, dp[i - k - 1]));
                }
                dp.push_back(cur);
            }
            return dp[n - 1];
        }
    };

  • 2

    This is an unnecessary amount of work for such a simple pattern...


  • 0
    T

    if k decreases from i/2, it will cost less time.


  • 0
    J

    Look at the results of the range from 2 to 6,you will find if n>4,the "n'' can split into two number. So the "k" of your codes can just decreaces from 4 when " i/2>4 ".


Log in to reply
 

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