Form N | Java code to find minimum cost to form a N - copy string ; Returns the minimum cost to form a n - copy string Here , x -> Cost to add / remove a single character ' G ' and y -> cost to append the string to itself ; Base Case : to form a 1 - copy string we need to perform an operation of type 1 ( i . e Add ) ; Case1 . Perform a Add operation on ( i - 1 ) - copy string , Case2 . Perform a type 2 operation on ( ( i + 1 ) / 2 ) - copy string ; Case1 . Perform a Add operation on ( i - 1 ) - copy string , Case2 . Perform a type 3 operation on ( i / 2 ) - copy string ; Driver Code
class Solution { static int findMinimumCost ( int n , int x , int y ) { int dp [ ] = new int [ n + 1 ] ; dp [ 1 ] = x ; for ( int i = 2 ; i <= n ; i ++ ) { if ( ( i & 1 ) != 0 ) { dp [ i ] = Math . min ( dp [ i - 1 ] + x , dp [ ( i + 1 ) / 2 ] + y + x ) ; } else { dp [ i ] = Math . min ( dp [ i - 1 ] + x , dp [ i / 2 ] + y ) ; } } return dp [ n ] ; } public static void main ( String args [ ] ) { int n = 4 , x = 2 , y = 1 ; System . out . println ( findMinimumCost ( n , x , y ) ) ; } }