int cutRod(vector<int> &price, int n)
{
	// since length array is not given therefore let us make one
    int length_cap[n];
    for(int i=1;i<=n;i++)
       length_cap[i-1]=i;
    
    // Here W->n , val[]->price[] , wt[]=>length[]
	
	// Now unbounded Knapsack as usual no changes
    int dp[n+1][n+1];
      for(int i=0;i<=n;i++)
        dp[i][0] = 0;
    
      for(int j=0;j<=n;j++)
        dp[0][j] = 0;
    
       for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(length_cap[i-1] <= j){    
              dp[i][j] = max(price[i-1] + dp[i][j-length_cap[i-1]], 
                             dp[i-1][j]);
            }
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    return dp[n][n];
}

int cutRodUtil(vector<int> &price, int maxLen, int n, vector<vector<int>> &cost)
{
    // Base condition.
    if (n <= 0 || maxLen <= 0)
    {
        return 0;
    }

    // Checks whether problem is already calculated or not.
    if (cost[n][maxLen] != -1)
    {
        return cost[n][maxLen];
    }

    /*
       If the length of the rod to be cut is less than or equal
       to the size of rod of length 'max_len',
       then depending on profit, either it will accept the cut or discard it.
    */
    if (n <= maxLen)
    {
        cost[n][maxLen] = max(price[n - 1] + cutRodUtil(price, maxLen - n, n, cost), cutRodUtil(price, maxLen, n - 1, cost));
    }

    /*
       If the length of the rod to be cut is
       greater than the size of rod of length
       'max_len', cutting is not permitted.
    */
    else
    {
        cost[n][maxLen] = cutRodUtil(price, maxLen, n - 1, cost);
    }

    return cost[n][maxLen];
}

int cutRod(vector<int> &price, int n)
{
    // Two state dp to store the sub-problems.
    vector<vector<int>> cost(n + 2, vector<int>(n + 2, -1));
    
    return cutRodUtil(price, n, n, cost);
}