Rod Cutting

problem id:--http://practice.geeksforgeeks.org/problems/rod-cutting/0

In this problem you have to use DP(instead of recursion which takes exponential time).
We create a array val of size n+1.
We then traverse var i from 1 to index n. And take i as the length of the Rod and try to find the max. Value for the regarding value. Answer can be that ith index value of using some combination of val array.


code:--

#include <bits/stdc++.h>
using namespace std;
#define sc(x)   scanf("%d",&x)
#define      rep(i, n)         for(int i = 0; i < (n); ++i)
#define rep2(i,j,n)   for(int i = j; i < (n); ++i)
int arr[105];
int n;
int solve()
{
int val[n+1]={0};
val[0]=0;
int Max;
for(int i=1;i<=n;++i)
{
Max=arr[i];
for(int j=1;j<i;++j) Max=max(Max,val[j]+val[i-j]);
val[i]=Max;
//debug2(i,Max);
}
//rep2(i,1,n+1) pf(val[i]);
return val[n];
}
int main()
{
int t;
sc(t);
while(t--)
{
cin>>n;
rep(i,n) sc(arr[i+1]);
printf("%d\n",solve());
}
return 0;
}