class Solution{
  public:
    int solve(int price[], int n , vector<int>& dp, int idx){
        if( idx >= n)   return 0;
        if(dp[idx] != -1) return dp[idx];
        int ans = 0;
        for(int i = 1; i <= n - idx; i++){
            ans = max(ans, price[i - 1] + solve(price, n , dp, idx + i));
        }
        return dp[idx] = ans;
    }
    int cutRod(int price[], int n) {
        //code here
        vector<int> dp;
        dp.resize(n, -1);
        return solve( price,n, dp, 0);
    }
};