Minimize cost to empty given array where cost of removing an element is its absolute difference with Time instant | Java program for the above approach ; Function to find the minimum cost to delete all array elements ; Sort the input array ; Store the maximum time to delete the array in the worst case ; Store the result in cost [ ] [ ] table ; Initialize the table cost [ ] [ ] ; Base Case ; Store the minimum of all cost values of the previous index ; Iterate from range [ 1 , n ] using variable i ; Update prev ; Iterate from range [ 1 , m ] using variable j ; Update cost [ i ] [ j ] ; Update the prev ; Store the minimum cost to delete all elements ; Find the minimum of all values of cost [ n ] [ j ] ; Print minimum cost ; Driver Code ; Function Call
import java . util . * ; import java . io . * ; class GFG { static int INF = 10000 ; static void minCost ( int arr [ ] , int n ) { Arrays . sort ( arr ) ; int m = 2 * n ; int cost [ ] [ ] = new int [ n + 1 ] [ m + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) { for ( int j = 0 ; j <= m ; j ++ ) { cost [ i ] [ j ] = INF ; } } cost [ 0 ] [ 0 ] = 0 ; int prev = 0 ; for ( int i = 1 ; i <= n ; i ++ ) { prev = cost [ i - 1 ] [ 0 ] ; for ( int j = 1 ; j <= m ; j ++ ) { cost [ i ] [ j ] = Math . min ( cost [ i ] [ j ] , prev + Math . abs ( j - arr [ i - 1 ] ) ) ; prev = Math . min ( prev , cost [ i - 1 ] [ j ] ) ; } } int minCost = INF ; for ( int j = 1 ; j <= m ; j ++ ) { minCost = Math . min ( minCost , cost [ n ] [ j ] ) ; } System . out . print ( minCost ) ; } public static void main ( String [ ] args ) { int arr [ ] = { 4 , 2 , 4 , 4 , 5 , 2 } ; int N = arr . length ; minCost ( arr , N ) ; } }