class Solution {
    
    public int minSteps(int n) {
        // initialize the dp table
        int[] memo = new int[n + 1];
        memo[n] = 0;
        
        for (int i = n - 1; i >= 1; i--) {
            // since we want the minimum answer among all candidates, 
            // the result is initially set to the maximum value.
            int res = Integer.MAX_VALUE;

            // extra is the len of the copied string, 
            // nPastes is the number of paste operations performed after the initial copy.
            int len = i;
            int extra = len, nPastes = 0;

            // repeat while we can successfully paste the text
            while (len + extra <= n) {
                // paste the text
                len += extra;
                nPastes++;

                // find answer for the remaining length
                int remain = memo[len];

                // if answer is found, update the current result
                if (remain != -1)
                    res = Math.min(res, nPastes + remain);
            }

            // if answer is not found, return -1,
            // else return result + 1 (plus one to consider the copy operation we performed initially)
            memo[i] = res == Integer.MAX_VALUE ? -1 : res + 1;
        }
        
        return memo[1];
    }
}