2 Keys Keyboard

Initially, on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:

1.Copy All: You can copy all the characters present on the notepad (a partial copy is not allowed).

2.Paste: You can paste the characters which are copied last time.

Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.

Example :

Input: 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'.

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

int dp[1001][1001];
int minStepsHelper(int Acount, int copyCount, int target)
{
    //If the A's count becomes same as the number of A's we need,
    // We return 1 because this was one way of copying and pasting
    if (Acount == target)
        return 1;

    //If the A's count goes beyond the number of A's we need,
    //we can return a large no. as its not a correct way of
    // copy pasting
    if (Acount > target)
        return 10e6;

    if (dp[Acount][copyCount] != -1)
        return dp[Acount][copyCount];

    //step1. to paste whatever was copied previously
    //(Add +1 because this counts as one step, we're only pasting )
    //step2.OR to copy all the A's and paste it (this counts as 2 steps,
    //copying and pasting, so we add +2.
     //answer is min of both the steps
    dp[Acount][copyCount] = min(minStepsHelper(Acount + copyCount, 
                            copyCount, target) + 1,
                                minStepsHelper(Acount * 2, 
                       Acount, target) + 2);
    return dp[Acount][copyCount];
}
int minSteps(int n)
{

    if (n == 1)
        return 0;
    memset(dp, -1, sizeof(dp));
    return minStepsHelper(1, 1, n);
}

int main()
{
    int n = 3;

    cout << minSteps(n);

    return 0;
}