Teaching Kids Programming – Top Down and Bottom Up Dynamic Programming Algorithm to Type N letters on a 2-keys Keyboard

Teaching Kids Programming: Videos on Data Structures and Algorithms

There is only one character ‘A’ on the screen of a notepad. You can perform two operations on this notepad for each step:

Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).
Paste: You can paste the characters which are copied last time.
Given an integer n, return the minimum number of operations to get the character ‘A’ exactly n times on the screen.

Example 1:
Input: n = 3
Output: 3
Explanation: Intitally, we have one character ‘A’.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get ‘AA’.
In step 3, we use Paste operation to get ‘AAA’.

Example 2:
Input: n = 1
Output: 0

We want to minimze the operations so that we need to have more letters in the buffer/clipboard and we then can Ctrl+C to copy the buffer in the clipboard and Ctrl+V to paste what we have. Given that we can only copy all the characters on screen to the clipboard, we want to find out the factors of N and obtained the minimal of them aka.

if i is a factor of n.

2-keys Keyboard via Top Down Dynamic Programming Algorithm

Top Down Dynamic Programming Algorithm is intuitive to implement via Recursion with Memoization:

1
2
3
4
5
6
7
8
9
10

class Solution:
    @cache
    def minSteps(self, n: int) -> int:
        if n == 1:
            return 0
        ans = n
        for i in range(2, n // 2 + 1):
            if n % i == 0: # if i is a factor of n
                ans = min(ans, self.minSteps(i) + n // i)
        return ans        

class Solution:
    @cache
    def minSteps(self, n: int) -> int:
        if n == 1:
            return 0
        ans = n
        for i in range(2, n // 2 + 1):
            if n % i == 0: # if i is a factor of n
                ans = min(ans, self.minSteps(i) + n // i)
        return ans        

The time complexity is O(N^2) and the space complexity is O(N) due to using cache to memoize the f(n) values. The slowest solution for N keys would be Copy Once and Paste N-1 times.

2-keys Keyboard via Bottom Up Dynamic Programming Algorithm

We can implement the same Dynamic Programming in the bottom-up manner, where we compute the dp values from small n to bigger n. We use array to store the intermediate dp values.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def minSteps(self, n: int) -> int:
        if n == 1:
            return 0
        dp = list(range(n + 1))
        for i in range(1, n + 1):
            for j in range(1, i // 2 + 1):
                if i % j == 0:
                    dp[i] = min(dp[i], dp[j] + i // j)
        return dp[n]        

class Solution:
    def minSteps(self, n: int) -> int:
        if n == 1:
            return 0
        dp = list(range(n + 1))
        for i in range(1, n + 1):
            for j in range(1, i // 2 + 1):
                if i % j == 0:
                    dp[i] = min(dp[i], dp[j] + i // j)
        return dp[n]        

The time complexity obviously is O(N^2) with two nested for loops, and the space complexity is O(N) because of the dp array.

–EOF (The Ultimate Computing & Technology Blog) —