• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
int minSteps(int n) {
if (n <= 1)
return 0;

// dp[i] := min steps to get i 'A'
vector<int> dp(n + 1);

// copy 'A', then paste 'A' i - 1 times
iota(begin(dp), end(dp), 0);

for (int i = 2; i <= n; ++i)
for (int j = i / 2; j > 2; --j)
if (i % j == 0) {
dp[i] = dp[j] + i / j;  // paste dp[j] i / j times
break;
}

return dp[n];
}
};
``````

## JAVA

``````class Solution {
public int minSteps(int n) {
// dp[i] := min steps to get i 'A'
int[] dp = new int[n + 1];

for (int i = 2; i <= n; ++i) {
dp[i] = i; // copy 'A', then paste 'A' i - 1 times
for (int j = i / 2; j > 2; --j)
if (i % j == 0) {
dp[i] = dp[j] + i / j; // paste dp[j] i / j times
break;
}
}

return dp[n];
}
}
``````

## Python

``````class Solution:
def minSteps(self, n: int) -> int:
if n <= 1:
return 0

# dp[i] := min steps to get i 'A'
# copy 'A', then paste 'A' i - 1 times
dp = [i for i in range(n + 1)]

for i in range(2, n + 1):
for j in range(i // 2, 2, -1):
if i % j == 0:
dp[i] = dp[j] + i // j  # paste dp[j] i / j times
break

return dp[n]
``````