Imagine you have a special keyboard with the following keys: 
Key 1:  Prints 'A' on screen
Key 2: (Ctrl-A): Select screen
Key 3: (Ctrl-C): Copy selection to buffer
Key 4: (Ctrl-V): Print buffer on screen appending it after what has already been printed. 
Find maximum numbers of A's that can be produced by pressing keys on the special keyboard N times. 
Example 1:
Input: N = 3
Output: 3
Explaination: Press key 1 three times.
Example 2:
Input: N = 7
Output: 9
Explaination: The best key sequence is 
key 1, key 1, key 1, key 2, key 3,
key4, key 4.
Your Task:
You do not need to read input or print anything. Your task is to complete the function optimalKeys() which takes N as input parameter and returns the maximum number of A's that can be on the screen after performing N operations.
Expected Time Complexity: O(N^{2})
Expected Auxiliary Space: O(N)
Constraints:
1 < N < 76

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Complete search

Starter code: #User function Template for python3



class Solution:

    def optimalKeys(self, N):

        # code here

Solutions:
class Solution:

	def optimalKeys(self, N):
		arr = [0] * N
		if N < 7:
			return N
		for i in range(1, 7):
			arr[i - 1] = i
		for i in range(7, N + 1):
			arr[i - 1] = max(2 * arr[i - 4], max(3 * arr[i - 5], 4 * arr[i - 6]))
		return arr[N - 1]


class Solution:

	def optimalKeys(self, N):
		l = [0] * 256
		l[0] = 0
		l[1] = 1
		l[2] = 2
		for i in range(3, N + 1):
			l[i] = i
			for j in range(i - 3, 0, -1):
				l[i] = max(l[i], l[j] + l[j] * (i - (2 + j)))
		return l[N]


class Solution:

	def optimalKeys(self, N):
		if N <= 6:
			return N
		screen = [0] * N
		for n in range(1, 7):
			screen[n - 1] = n
		for n in range(7, N + 1):
			screen[n - 1] = 0
			for b in range(n - 3, 0, -1):
				curr = (n - b - 1) * screen[b - 1]
				if curr > screen[n - 1]:
					screen[n - 1] = curr
		return screen[N - 1]


class Solution:

	def optimalKeys(self, N):
		if N <= 6:
			return N
		dp = [0 for i in range(N + 1)]
		for i in range(1, N + 1):
			dp[i] = i
		for i in range(7, N + 1):
			j = i - 3
			while j >= 1:
				curr = dp[j] * (i - j - 1)
				if curr > dp[i]:
					dp[i] = curr
				j -= 1
		return dp[N]


class Solution:

	def optimalKeys(self, N):
		res = [-1] * N
		return self.optimal(res, N)

	def optimal(self, res, n):
		if n < 7:
			return n
		i = n - 3
		temp1 = 2
		ans = 0
		while i >= 0:
			if res[i] == -1:
				res[i] = self.optimal(res, i)
			ans = max(ans, temp1 * res[i])
			temp1 += 1
			i -= 1
		return ans


class Solution:

	def optimalKeys(self, N):
		if N < 7:
			return N
		return self.support(N)

	def support(self, N):
		dp = [0] * (N + 1)
		for i in range(7):
			dp[i] = i
		for i in range(7, N + 1):
			res = 0
			for j in range(i - 3, 1, -1):
				res = max(res, dp[j] * (i - j - 1))
			dp[i] = res
		return dp[N]


class Solution:

	def optimalKeys(self, N):
		if N <= 6:
			return N
		d = [0 for i in range(N + 1)]
		for i in range(1, 7):
			d[i] = i
		for i in range(7, N + 1):
			for j in range(i - 3, 0, -1):
				c = d[j] * (i - j - 1)
				if c > d[i]:
					d[i] = c
		return d[N]


class Solution:

	def optimalKeys(self, N):
		dp = [[1, 0, 0, 0, 0]]
		for i in range(1, N):
			pre = dp[-1]
			dp1 = max(pre[:-1]) + 1
			dp2 = max(pre[:-1])
			dp3 = pre[1]
			(dp4, dp5) = (0, 0)
			for j in range(i):
				if (i - j + 1) * dp[j][2] >= dp4:
					(dp4, dp5) = ((i - j + 1) * dp[j][2], dp[j][2])
			dp.append([dp1, dp2, dp3, dp4, dp5])
		return max(dp[-1])


class Solution:

	def optimalKeys(self, N):
		self.arr = [0] * (N + 1)
		return self.recur(N)

	def recur(self, N):
		if N <= 6:
			return N
		if self.arr[N]:
			return self.arr[N]
		x = 0
		for i in range(N, 6 - 1, -1):
			x = max(x, (N - i + 2) * self.recur(i - 3))
		self.arr[N] = x
		return x


class Solution:

	def optimalKeys(self, N):
		if N <= 6:
			return N
		dp = [-1] * (N + 1)
		for i in range(7):
			dp[i] = i
		for i in range(7, N + 1):
			multiple = 2
			for j in range(i - 3, 0, -1):
				dp[i] = max(dp[i], dp[j] * multiple)
				multiple += 1
		return dp[-1]


class Solution:

	def optimalKeys(self, N):
		if N <= 6:
			return N
		if N == 11:
			return 27
		dp = [-1] * (N + 1)
		maxx = 0
		x = 2
		y = N - 3
		for i in range(7):
			dp[i] = i
		for i in range(7, N + 1):
			multiple = 2
			for j in range(i - 3, 0, -1):
				dp[i] = max(dp[i], dp[j] * multiple)
				multiple += 1
		return dp[-1]


class Solution:

	def optimalKeys(self, N):
		if N <= 6:
			return N
		screen = [0] * N
		for n in range(1, 7):
			screen[n - 1] = n
		for n in range(7, N + 1):
			screen[n - 1] = max(2 * screen[n - 4], max(3 * screen[n - 5], 4 * screen[n - 6]))
		return screen[N - 1]


class Solution:

	def findVal(self, n):
		if n <= 6:
			return n
		if n in self.dp:
			return self.dp[n]
		maxi = 0
		for b in range(n - 3, 0, -1):
			maxi = max(maxi, (n - b - 1) * self.findVal(b))
		self.dp[n] = maxi
		return maxi

	def optimalKeys(self, n):
		self.dp = {}
		return self.findVal(n)


class Solution:

	def optimalKeys(self, N):
		if N <= 1:
			return N
		dp = [0] * (N + 1)
		dp[1] = 1
		for i in range(2, N + 1):
			dp[i] = dp[i - 1] + 1
			for j in range(2, i):
				dp[i] = max(dp[i], dp[j - 2] * (i - j + 1))
		return dp[N]


class Solution:

	def util(self, n, copied, i, prev, dp):
		if i <= 0:
			return 0
		if dp[i] != -1:
			return dp[i]
		res = self.util(n, False, i - 1, prev + 1, dp) + 1
		val = 0
		if copied:
			val += self.util(n, True, i - 1, prev, dp) + prev
		ans = 0
		if i >= 2 and prev > 0:
			ans += self.util(n, True, i - 2, prev, dp) + 0
		dp[i] = max(res, ans, val)
		return dp[i]

	def optimalKeys(self, n):
		dp = [i for i in range(n + 1)]
		if n <= 6:
			return n
		for i in range(7, n + 1):
			dp[i] = max(2 * dp[i - 3], 3 * dp[i - 4], 4 * dp[i - 5])
		return dp[n]


class Solution:

	def optimalKeys(self, N):
		cache = {}

		def dfs(N):
			if N in cache:
				return cache[N]
			max_ = N
			for i in range(N - 2):
				max_ = max(max_, dfs(i) * (N - i - 1))
			cache[N] = max_
			return max_
		return dfs(N)


class Solution:

	def optimalKeys(self, N):
		if N <= 6:
			return N
		screen = [0] * N
		for i in range(1, 7):
			screen[i - 1] = i
		for i in range(7, N + 1):
			screen[i - 1] = 0
			for j in range(i - 3, 0, -1):
				cur = (i - j - 1) * screen[j - 1]
				if cur > screen[i - 1]:
					screen[i - 1] = cur
		return screen[N - 1]


class Solution:

	def optimalKeys(self, N):
		self.state = [-1] * (N + 1)
		return self.keys(N)

	def keys(self, N):
		if N <= 6:
			return N
		if self.state[N] != -1:
			return self.state[N]
		ans = 0
		times = 2
		for i in range(N - 3, 0, -1):
			if self.state[i] == -1:
				self.state[i] = self.keys(i)
			res = self.state[i] * times
			ans = max(res, ans)
			times += 1
		self.state[N] = ans
		return ans


class Solution:

	def optimalKeys(self, n):
		dp = [0] * (n + 1)
		for i in range(1, n + 1):
			dp[i] = dp[i - 1] + 1
			for j in range(1, i - 2):
				dp[i] = max(dp[i], dp[j] * (i - j - 1))
		return dp[n]


class Solution:

	def optimalKeys(self, n):
		if n < 7:
			return n
		dp = [-1] * (n + 1)
		for i in range(7):
			dp[i] = i
		for i in range(7, n + 1):
			curr = -1
			for j in range(1, i - 2):
				curr = max(curr, dp[j] * (i - j - 1))
			dp[i] = curr
		return dp[n]


class Solution:

	def recur(self, ans, cnt, N, l):
		if N < 0:
			return
		if N == 0:
			ans[0] = max(ans[0], cnt)
			return ans
		self.recur(ans, cnt + l, N - 1, l)
		l = cnt
		cnt = cnt + l
		self.recur(ans, cnt, N - 3, l)

	def optimalKeys(self, N):
		dp = [0 for _ in range(N + 1)]
		if N <= 6:
			return N
		for i in range(0, 7):
			dp[i] = i
		for i in range(7, N + 1):
			for j in range(i - 3, 0, -1):
				curr = dp[j] * (i - j - 1)
				dp[i] = max(curr, dp[i])
		return dp[N]


class Solution:

	def optimalKeys(self, n):
		if n < 5:
			return n
		else:
			return max(4 * self.optimalKeys(n - 5), 3 * self.optimalKeys(n - 4))


class Solution:

	def optimalKeys(self, N):
		n = N
		if N < 7:
			return N
		dp = [0] * (n + 1)
		for i in range(1, 7):
			dp[i] = i
		for i in range(7, N + 1):
			dp[i] = max(2 * dp[i - 3], 3 * dp[i - 4], 4 * dp[i - 5])
		return dp[-1]


class Solution:

	def optimalKeys(self, N):
		if N < 7:
			return N
		arr = [0 for _ in range(N)]
		for i in range(6):
			arr[i] = i + 1
		for i in range(6, N):
			for j in range(i - 3, -1, -1):
				arr[i] = max(arr[i], arr[j] * (i - j - 1))
		return arr[N - 1]


class Solution:

	def optimalKeys(self, N):
		dparr = [i for i in range(N + 1)]
		for i in range(7, N + 1):
			k = 2
			temp = []
			for j in range(i - 3, 0, -1):
				temp.append(dparr[j] * k)
				k += 1
			dparr[i] = max(temp)
		return dparr[-1]


class Solution:

	def optimalKeys(self, N):
		dp = [-1] * (N + 1)
		dp[0] = 0

		def findsol(n):
			if n <= 6:
				return n
			if dp[n] != -1:
				return dp[n]
			maxe = 0
			times = 2
			for i in range(n - 3, 0, -1):
				maxe = max(maxe, times * findsol(i))
				times += 1
			dp[n] = maxe
			return maxe
		return findsol(N)


class Solution:

	def optimalKeys(self, N):
		buf = {}

		def ops(n):
			code = '' + str(n)
			if code in buf:
				return buf[code]
			if n == 0:
				return 0
			if n == 1:
				return 1
			if n < 6:
				return n
			options = []
			options.append(ops(n - 1) + 1)
			for i in range(3, 10):
				if n - i >= 0:
					options.append(ops(n - i) * (i - 1))
			ans = max(options)
			buf[code] = ans
			return ans
		return ops(N)


class Solution:

	def optimalKeys(self, N):
		dp = [0 for i in range(N + 1)]
		for i in range(1, N + 1):
			if i <= 6:
				dp[i] = i
			else:
				j = i - 3
				temp = 0
				while j >= 1:
					temp = max(temp, dp[j] * (i - j - 1))
					j -= 1
				dp[i] = temp
		return dp[N]


class Solution:

	def optimalKeys(self, N):
		if N <= 5:
			return N
		dp = [0] * (N + 1)
		dp[1] = 1
		dp[2] = 2
		dp[3] = 3
		dp[4] = 4
		dp[5] = 5
		for i in range(6, N + 1):
			choices = [i]
			for k in range(2, i - 1):
				choices.append(k * dp[i - k - 1])
			dp[i] = max(choices)
		return dp[N]


class Solution:

	def optimalKeys(self, n):
		l = [0, 1, 2, 3, 4, 5, 6]
		for i in range(7, n + 1):
			m = i
			c = 2
			for j in range(i - 3, 0, -1):
				x = l[j] * c
				if x >= m:
					m = x
				else:
					break
				c += 1
			l.append(m)
		return l[n]


class Solution:

	def find_optimal(self, N, dp):
		if N <= 6:
			return N
		if dp[N] != -1:
			return dp[N]
		max_count = 0
		for b in range(N - 3, 0, -1):
			count = (N - b - 1) * self.find_optimal(b, dp)
			max_count = max(max_count, count)
		dp[N] = max_count
		return dp[N]

	def optimalKeys(self, N):
		if N <= 6:
			return N
		dp = [-1] * (N + 1)
		for i in range(1, 7):
			dp[i] = i
		for i in range(7, N + 1):
			for b in range(i - 3, 0, -1):
				dp[i] = max(dp[i], (i - b - 1) * dp[b])
		return dp[N]


class Solution:

	def helper(self, N, dp):
		if N <= 6:
			return N
		if dp[N] != -1:
			return dp[N]
		max_count = 0
		for b in range(N - 3, 0, -1):
			count = (N - b - 1) * self.helper(b, dp)
			max_count = max(max_count, count)
		dp[N] = max_count
		return dp[N]

	def optimalKeys(self, N):
		dp = [-1] * (N + 1)
		return self.helper(N, dp)


import math

class Solution:

	def optimalKeys(self, N):
		if N <= 6:
			return N
		dp = [0 for i in range(N + 1)]
		for i in range(1, 7):
			dp[i] = i
		for i in range(7, N + 1):
			for j in range(i - 3, 0, -1):
				dp[i] = max(dp[i], dp[j] * (i - j - 1))
		return dp[N]


class Solution:

	def optimalKeys(self, N):
		if N < 7:
			return N
		cnt = [0] * N
		for i in range(1, 7):
			cnt[i - 1] = i
		for i in range(7, N + 1):
			for b in range(i - 3, 0, -1):
				curr = (i - b - 1) * cnt[b - 1]
				if curr > cnt[i - 1]:
					cnt[i - 1] = curr
		return cnt[-1]


class Solution:
	dp = [None for i in range(76)]
	(dp[0], dp[1], dp[2], dp[3], dp[4]) = (0, 1, 2, 3, 4)
	for i in range(5, 76):
		dp[i] = max(2 * dp[i - 3], 3 * dp[i - 4], 4 * dp[i - 5])

	def optimalKeys(self, N):
		return self.dp[N]


class Solution:

	def optimalKeys(self, N):
		if N <= 6:
			return N
		dp = [0] * N
		for i in range(1, 7):
			dp[i - 1] = i
		for i in range(7, N + 1):
			dp[i - 1] = 0
			for b in range(i - 3, 0, -1):
				current = (i - b - 1) * dp[b - 1]
				dp[i - 1] = max(current, dp[i - 1])
		return dp[N - 1]


class Solution:

	def __init__(self):
		self.keys = {}
		for i in range(1, 76):
			self.optimalKeys1(i)

	def optimalKeys1(self, N):
		if N <= 5:
			self.keys[N] = N
			return N
		else:
			val = max(self.keys[N - 1] + 1, self.keys[N - 2] + 2, 2 * self.keys[N - 3], 3 * self.keys[N - 4], 4 * self.keys[N - 5])
			self.keys[N] = val

	def optimalKeys(self, N):
		return self.keys[N]


class Solution:

	def optimalKeys(self, n):
		if n <= 6:
			return n
		temp = [0] * n
		for i in range(1, 7):
			temp[i - 1] = i
		for i in range(7, n + 1):
			for j in range(n - 3, 0, -1):
				cur = (i - j - 1) * temp[j - 1]
				if cur > temp[i - 1]:
					temp[i - 1] = cur
		return temp[n - 1]


class Solution:

	def optimalKeys(self, N):
		arr = [0, 1, 2, 3, 4, 5, 6]
		for i in range(7, N + 1):
			arr.append(0)
			c = 2
			for j in range(i - 3, 0, -1):
				if arr[i] <= arr[j] * c:
					arr[i] = arr[j] * c
				else:
					break
				c += 1
		return arr[N]


class Solution:

	def optimalKeys(self, N):
		if N <= 6:
			return N
		screen = [0] * N
		for n in range(1, 7):
			screen[n - 1] = n
		for n in range(7, N + 1):
			screen[n - 1] = 0
			for b in range(n - 3, 0, -1):
				curr = (n - b - 1) * screen[b - 1]
				if curr > screen[n - 1]:
					screen[n - 1] = curr
		return screen[N - 1]
		if n <= 6:
			return n
		temp = [0] * n
		for i in range(1, 7):
			temp[i - 1] = i
		for i in range(7, n + 1):
			temp[i - 1] = 0
			for j in range(n - 3, 0, -1):
				cur = (n - j - 1) * temp[j - 1]
				if cur > temp[i - 1]:
					temp[i - 1] = cur
		return temp[n - 1]


class Solution:

	def optimalKeys(self, N):
		if N <= 6:
			return N
		dp = [i if i <= 6 else 0 for i in range(N + 1)]
		for i in range(7, N + 1):
			c = 2
			for j in range(i - 3, 0, -1):
				if dp[j] * c >= dp[i]:
					dp[i] = dp[j] * c
				else:
					break
				c += 1
		return dp[N]


class Solution:

	def optimalKeys(self, N):
		dp = [0 for i in range(N + 1)]
		if N <= 6:
			return N
		for i in range(7):
			dp[i] = i
		for i in range(7, N + 1):
			max1 = i
			dp[i] = i
			for j in range(1, i - 2):
				if max1 < dp[j] * (i - 2 - j + 1):
					max1 = dp[j] * (i - 2 - j + 1)
			dp[i] = max1
		return dp[N]


from functools import lru_cache

class Solution:

	def optimalKeys(self, n):
		arr = [0, 1, 2, 3, 4, 5, 6]
		for i in range(7, N + 1):
			ans = max(arr[i - 4] * 3, arr[i - 5] * 4)
			arr.append(ans)
		return arr[N]


from functools import lru_cache

class Solution:

	def optimalKeys(self, n):

		@lru_cache(None)
		def key(n):
			if n <= 6:
				return n
			maxi = 0
			for b in range(n - 3, 0, -1):
				curr = (n - b - 1) * key(b)
				if curr > maxi:
					maxi = curr
			return maxi
		if n <= 6:
			return n
		maxi = 0
		return key(n)


class Solution:

	def maximumA(self, N, map):
		if N in map:
			return map[N]
		if N <= 6:
			map[N] = N
			return N
		maxi = -1
		for i in range(2, N):
			maxi = max(maxi, (N - i) * self.maximumA(i - 1, map))
		map[N] = maxi
		return maxi

	def optimalKeys(self, N):
		return self.maximumA(N, {})


class Solution:

	def optimalKeys(self, N):
		dp = [i for i in range(N + 1)]
		for i in range(1, N + 1):
			dp[i] = dp[i - 1] + 1
			for j in range(3, i):
				dp[i] = max(dp[i], (i - j) * dp[j - 1])
		return dp[N]


from functools import lru_cache

class Solution:

	def optimalKeys(self, N):
		dp = [i for i in range(N + 1)]
		for i in range(1, N + 1):
			dp[i] = dp[i - 1] + 1
			for j in range(3, i):
				dp[i] = max(dp[i], (i - j) * dp[j - 1])
		return dp[N]


from functools import lru_cache

class Solution:

	def optimalKeys(self, N):

		@lru_cache(None)
		def sol(N):
			if N <= 6:
				return N
			ans = sol(N - 1) + 1
			for i in range(3, N):
				if i >= N:
					break
				ans = max(ans, (N - i) * sol(i - 1))
			return ans
		return sol(N)


from functools import lru_cache

class Solution:

	def optimalKeys(self, N):

		@lru_cache(None)
		def tr(n):
			if n <= 6:
				return n
			val = tr(n - 1) + 1
			for i in range(n - 3, 0, -1):
				val = max(val, tr(i) * (n - i - 1))
			return val
		return tr(N)


class Solution:

	def optimalKeys(self, n):
		if n <= 6:
			return n
		else:
			dp = [0 for i in range(n + 1)]
			for i in range(7):
				dp[i] = i
			for i in range(7, n + 1):
				for j in range(3, i):
					dp[i] = max(dp[i], dp[i - 1] + 1, dp[i - j] * (j - 1))
			return dp[n]


class Solution:

	def helper(self, n):
		if n <= 6:
			return n
		if self.dp[n] != -1:
			return self.dp[n]
		ans = 0
		for i in range(n - 3, 0, -1):
			temp = (n - i - 1) * self.helper(i)
			ans = max(ans, temp)
		self.dp[n] = ans
		return self.dp[n]

	def optimalKeys(self, n):
		self.dp = [-1] * (n + 1)
		return self.helper(n)