Q21 Rod Cutting | Practice | GeeksforGeeks
Fri Mar 24 2023 07:14:52 GMT+0000 (Coordinated Universal Time)
Saved by
@Ayush_dabas07
//{ Driver Code Starts
import java.io.*;
import java.util.*;
class RodCutting {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
int n = sc.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = sc.nextInt();
Solution ob = new Solution();
System.out.println(ob.cutRod(arr, n));
}
}
}
// } Driver Code Ends
class Solution{
public int cutRod(int price[], int n) {
/* storage and meaning - every cell denotes maximum profit if the rod had been of
that length
*/
int dp[] = new int[n+1];
int nprice[] = new int[n+1]; //for ease of indexing
//copying all prices in 1 based indexing
for(int i = 1 ; i < n+1 ; i++)
nprice[i] = price[i-1];
//dp of 0 is already 0
dp[1] = nprice[1]; //1 length of rod can only be sold for price of 1 length
for(int i = 2 ; i < n+1 ; i++){
//storing profit when rod is not cut at all and sold at full length of i only
int maxProfit = nprice[i];
//cutting rod in 1 to i-1 pieces and checking for max profit
//with optimized i-j
for(int j = 1 ;j < i ; j++ )
maxProfit = Math.max(maxProfit , dp[i-j] + nprice[j]);
//or
//this will be cutting in j and taking cartesian product of optimized j &
//optimized i-j , we only have to travel till half as then pairs will get repeated
// for(int j = 1 ;j <= i/2 ; j++ )
// maxProfit = Math.max(maxProfit , dp[i-j] + dp[j]);
dp[i] = maxProfit;
}
// for(int i = 0 ; i < n+1 ; i ++)
// System.out.print(dp[i] + " ");
return dp[n];
}
}
content_copyCOPY
https://practice.geeksforgeeks.org/problems/rod-cutting0840/1
Comments