<p>Given an integer <code>n</code>, break it into the sum of <code>k</code> <strong>positive integers</strong>, where <code>k &gt;= 2</code>, and maximize the product of those integers.</p>

<p>Return <em>the maximum product you can get</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 1
<strong>Explanation:</strong> 2 = 1 + 1, 1 &times; 1 = 1.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 10
<strong>Output:</strong> 36
<strong>Explanation:</strong> 10 = 3 + 3 + 4, 3 &times; 3 &times; 4 = 36.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 58</code></li>
</ul>

#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int f(int i,int sum,vector<int> &v,int n, vector<vector<int>> &dp) {
        if(i >= v.size() || sum == n) return 1;
        if(sum > n) return 0;

       if(dp[i][sum] != -1) return dp[i][sum];
       if(v[i]+sum <= n){
        return max(v[i]*f(i,sum+v[i],v,n,dp),f(i+1,sum,v,n,dp));
       }
       else{
        return f(i+1,sum,v,n,dp);
       }
       
    }

    int integerBreak(int n) {
    vector<int>v;
    for(int i=1;i<n;i++) v.push_back(i);
    int m = v.size();
    vector<vector<int>> dp(m,vector<int>(n+1,-1));
     return f(1,0,v,n,dp);
        
    }
};

8200