ROD CUTTING: Dynamic Programming

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

#define endl "\n"

ll arr[1009];

ll n;

ll dp[1009];

ll rod(ll len)

{

    if(len==0)return 0;

    if(dp[len]!=-1)return dp[len];

    ll mx;

    mx=0;

    for(ll i=1;i<=n;i++)

    {

        if(len-i>=0)

        {

            mx=max(mx,rod(len-i)+arr[i-1]);

        }

    }

    return dp[len]=mx;

}

int main()

{

   ios_base::sync_with_stdio(0);

   cin.tie(0);

   cout.tie(0);

   ll i;

   cin>>n;

  memset(dp,-1,sizeof(dp));

   for(i=0;i<n;i++)cin>>arr[i];

  cout<<rod(n)<<endl;

    return 0;

}