Integer Break Solutions in C++

// Source : https://leetcode.com/problems/integer-break/
// Author : Hao Chen
// Date   : 2016-05-29



class Solution {
public:
    // As the hint said, checking the n with ranging from 7 to 10 to discover the regularities.
    // n = 7,    3*4 = 12
    // n = 8,  3*3*2 = 18
    // n = 9,  3*3*3 = 27
    // n = 10, 3*3*4 = 36
    // n = 11, 3*3*3*2 = 54
    //
    // we can see we can break the number by 3 if it is greater than 4;
    //
    int integerBreak(int n) {
        if ( n == 2 ) return 1;
        if ( n == 3 ) return 2;
        int result = 1;
        while( n > 4 ) {
            result *= 3;
            n -= 3;
        }
        result *= n;
        return result;
    }
};

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

/// Source : https://leetcode.com/problems/integer-break/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/// Memory Search
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {
private:
    vector<int> memo;

    int max3(int a, int b, int c){
        return max(a, max(b, c));
    }

    int breakInteger(int n){

        if(n == 1)
            return 1;

        if(memo[n] != -1)
            return memo[n];

        int res = -1;
        for(int i = 1 ; i <= n - 1 ; i ++)
            res = max3(res, i * (n - i) , i * breakInteger(n - i));
        memo[n] = res;
        return res;
    }

public:
    int integerBreak(int n) {
        assert(n >= 1);
        memo.clear();
        for(int i = 0 ; i < n + 1 ; i ++)
            memo.push_back(-1);
        return breakInteger(n);
    }
};


int main() {

    cout << Solution().integerBreak(2) << endl;
    cout << Solution().integerBreak(10) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/integer-break/description/
/// Author : liuyubobobo
/// Time   : 2017-11-19

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

private:
    int max3(int a, int b, int c ){
        return max(max(a, b), c);
    }

public:
    int integerBreak(int n) {

        assert(n >= 1);

        vector<int> memo(n + 1, -1);

        memo[1] = 1;
        for(int i = 2 ; i <= n ; i ++)
            for(int j = 1 ; j <= i - 1 ; j ++)
                memo[i] = max3(memo[i], j * (i - j), j * memo[i - j]);

        return memo[n];
    }
};


int main() {

    cout << Solution().integerBreak(2) << endl;
    cout << Solution().integerBreak(3) << endl;
    cout << Solution().integerBreak(4) << endl;
    cout << Solution().integerBreak(10) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/integer-break/description/
/// Author : liuyubobobo
/// Time   : 2019-07-24

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// Deal with 2, 3 and 4 seperately
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

public:
    int integerBreak(int n) {

        assert(n >= 1);
        if(n == 2) return 1;
        if(n == 3) return 2;

        vector<int> memo(n + 1, -1);
        memo[0] = 0;
        memo[1] = 1;
        memo[2] = 2;
        memo[3] = 3;
        for(int i = 2 ; i <= n ; i ++)
            for(int j = 1 ; j <= i / 2 ; j ++)
                memo[i] = max(memo[i], memo[j] * memo[i - j]);

        return memo[n];
    }
};


int main() {

    cout << Solution().integerBreak(2) << endl;
    cout << Solution().integerBreak(3) << endl;
    cout << Solution().integerBreak(4) << endl;
    cout << Solution().integerBreak(10) << endl;

    return 0;
}