rod-cutting

/*Given a rod of length N inches and an array of prices, price[] that contains prices of all pieces of size smaller than N. Determine the maximum value obtainable by cutting up the rod and selling the pieces.

Example 1:

Input:
N = 8
Price[] = {1, 5, 8, 9, 10, 17, 17, 20}
Output:
22
Explanation:
The maximum obtainable value is 22 by
cutting in two pieces of lengths 2 and 
6, i.e., 5+17=22.
Example 2:

Input:
N=8
Price[] = {3, 5, 8, 9, 10, 17, 17, 20}
Output: 24
Explanation: 
The maximum obtainable value is 
24 by cutting the rod into 8 pieces 
of length 1, i.e, 8*3=24. 

Your Task:  
You don't need to read input or print anything. Your task is to complete the function cutRod() which takes the array A[] and its size N as inputs and returns the maximum price obtainable.


Expected Time Complexity: O(N2)
Expected Auxiliary Space: O(N)


Constraints:
1 ≤ N ≤ 1000
1 ≤ Ai ≤ 105*/


//Solution

#include <iostream>
using namespace std;
int t[9][9];
int un_kp(int price[], int length[],
					int Max_len, int n)
{

	if (n == 0 || Max_len == 0)
	{
		return 0;
	}
	if (length[n - 1] <= Max_len)
	{
		t[n][Max_len]
			= max(price[n - 1]
					+ un_kp(price, length,
						Max_len - length[n - 1], n),
				un_kp(price, length, Max_len, n - 1));
	}
	else
	{
		t[n][Max_len]
			= un_kp(price, length,
							Max_len, n - 1);
	}

	return t[n][Max_len];
}
test above functions */
int main()
{
	int price[] = { 1, 5, 8, 9, 10, 17, 17, 20 };
	int n = sizeof(price) / sizeof(price[0]);
	int length[n];
	for (int i = 0; i < n; i++) {
		length[i] = i + 1;
	}
	int Max_len = n;
	cout << "Maximum obtained value is "
		<< un_kp(price, length, n, Max_len) << endl;
}