650. 2 Keys Keyboard | LeetCode | Recursion, DP Solution C++

 650. 2 Keys Keyboard

There is only one character 'A' on the screen of a notepad. You can perform one of 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: Initially, 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

 

Constraints:

• 1 <= n <= 1000

Solution-

We can start with a recursive solution where we will pass the current length, copy string length, and the number of steps. If we reach our required length then we will store it in our answer else if we exceed it then we will simply discard it.

We can optimize it by just changing a few things like instead of copying only in one recursion call we can copy and paste it using two steps. 

Now we can optimize further by using dp as we will make a 2D dp and we know that only steps and the length of the string are changing we can use it. If the current length and steps have already been calculated we don't need to calculate it once more.

Optimizing it furthermore we can do it using some maths. Suppose we need the length to be 6 and we know that 6 is divisible by 3 so we can use the fact that we can copy length 3 in one step and then add it in one step, so the total will be dp[3]+1+1 i.e dp[3]+6/3, i.e dp[j]+j/i.