You are given time for insertion, deletion and copying, the task is to calculate the minimum time to write N characters on the screen using these operations. Each time you can insert a character, delete the last character and copy and paste all written characters i.e. after copy operation count of total written character will become twice.
Example 1:
Input: N = 9, I = 1, D = 2, C = 1  
Output: 5
Explanation: N characters can be written
on screen in 5 time units as shown below,
insert a character    
characters = 1,  total time = 1
again insert character      
characters = 2,  total time = 2
copy characters             
characters = 4,  total time = 3
copy characters             
characters = 8,  total time = 4
insert character           
characters = 9,  total time = 5
Example 2:
Input: N = 1, I = 10, D = 1, C = 5
Output: 10
Explanation: Insert one character
Your Task:  
You don't need to read input or print anything. Complete the function minTimeForWritingChars() which takes N, I, D and C as input parameters and returns the integer value
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Starter code: #User function Template for python3
class Solution:
	def minTimeForWritingChars(self, N, I, D, C):
		# code here

Solutions:
class Solution:

	def minTimeForWritingChars(self, N, I, D, C):
		dp = [0] * (N + 1)
		dp[1] = I
		for i in range(2, N + 1):
			dp[i] = dp[i - 1] + I
			if i % 2 == 0:
				dp[i] = min(dp[i], dp[i // 2] + C)
			else:
				dp[i] = min(dp[i], dp[i // 2 + 1] + C + D)
		return dp[-1]


class Solution:

	def minTimeForWritingChars(self, N, I, D, C):
		n = N
		insert_time = I
		removal_time = D
		copy_time = C
		dp = [0] * (n + 1)
		dp[1] = insert_time
		for i in range(1, n + 1):
			if i % 2 == 0:
				dp[i] = min(dp[i - 1] + insert_time, dp[i // 2] + copy_time)
			else:
				dp[i] = min(dp[i - 1] + insert_time, dp[(i + 1) // 2] + copy_time + removal_time)
		return dp[-1]