Minimum time to write characters using insert , delete and copy operation | C ++ program to write characters in minimum time by inserting , removing and copying operation ; method returns minimum time to write ' N ' characters ; declare dp array and initialize with zero ; first char will always take insertion time ; loop for ' N ' number of times ; if current char count is even then choose minimum from result for ( i - 1 ) chars and time for insertion and result for half of chars and time for copy ; if current char count is odd then choose minimum from result for ( i - 1 ) chars and time for insertion and result for half of chars and time for copy and one extra character deletion ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minTimeForWritingChars ( int N , int insert , int remove , int copy ) { if ( N == 0 ) return 0 ; if ( N == 1 ) return insert ; int dp [ N + 1 ] ; memset ( dp , 0 , sizeof ( dp ) ) ; dp [ 1 ] = insert ; for ( int i = 2 ; i <= N ; i ++ ) { if ( i % 2 == 0 ) dp [ i ] = min ( dp [ i - 1 ] + insert , dp [ i / 2 ] + copy ) ; else dp [ i ] = min ( dp [ i - 1 ] + insert , dp [ ( i + 1 ) / 2 ] + copy + remove ) ; } return dp [ N ] ; } int main ( ) { int N = 9 ; int insert = 1 , remove = 2 , copy = 1 ; cout << minTimeForWritingChars ( N , insert , remove , copy ) ; return 0 ; }