Dynamic Programming 13

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.

Problem link :- click here

Code

import java.util.Scanner;

public class DynamicProgramming_13
{
	
	//Recursion and Memoization
	static int maxAmount(int price[], int n, int memo[])
	{
		if(memo[n] != 0)
			return memo[n];
		
		if(n==0  ||  n==1)
			return price[n];
		
		int max = 0;
		int cur = 0;
		for(int i=1; i<=n; i++)
		{
			cur = price[i] + maxAmount(price, n-i, memo);
			if(cur > max)
				max = cur;
		}
		
		memo[n] = max;
		return max;
	}
	
	//DP
	static int maxAmount1(int price[], int n)
	{
		int dp_arr[] = new int[n+1];
		
		for(int i=0; i<=n; i++)
			dp_arr[i] = price[i];
		
		for(int i=2; i<=n; i++)
		{
			for(int j=1; j<i; j++)
			{
				int amt = price[j] + dp_arr[i-j];
				if( amt > dp_arr[i] )
					dp_arr[i] = amt;
			}
		}
		
		for(int x: dp_arr)
			System.out.print(x + "\t");
		
		return dp_arr[n];
	}

	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		
		System.out.print("Enter the size of the rod : ");
		int n = s.nextInt();
		int price[] = new int[n+1];
		
		System.out.println("Enter the price list : ");
		for(int i=1; i<n; i++)
			price[i] = s.nextInt();
		
//		int memo[] = new int[n+1];
		int ans = maxAmount1(price, n);
		System.out.println("\n\n" + ans);
		
		s.close();
	}

}