Minimum time to write characters using insert , delete and copy operation | Python3 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
def minTimeForWritingChars ( N , insert , remov , cpy ) : NEW_LINE INDENT if N == 0 : NEW_LINE INDENT return 0 NEW_LINE DEDENT if N == 1 : NEW_LINE INDENT return insert NEW_LINE DEDENT dp = [ 0 ] * ( N + 1 ) NEW_LINE dp [ 1 ] = insert NEW_LINE for i in range ( 2 , N + 1 ) : NEW_LINE INDENT if i % 2 == 0 : NEW_LINE INDENT dp [ i ] = min ( dp [ i - 1 ] + insert , dp [ i // 2 ] + cpy ) NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = min ( dp [ i - 1 ] + insert , dp [ ( i + 1 ) // 2 ] + cpy + remov ) NEW_LINE DEDENT DEDENT return dp [ N ] NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 9 NEW_LINE insert = 1 NEW_LINE remov = 2 NEW_LINE cpy = 1 NEW_LINE print ( minTimeForWritingChars ( N , insert , remov , cpy ) ) NEW_LINE DEDENT