<p>There is only one character <code>&#39;A&#39;</code> on the screen of a notepad. You can perform one of two operations on this notepad for each step:</p>

<ul>
	<li>Copy All: You can copy all the characters present on the screen (a partial copy is not allowed).</li>
	<li>Paste: You can paste the characters which are copied last time.</li>
</ul>

<p>Given an integer <code>n</code>, return <em>the minimum number of operations to get the character</em> <code>&#39;A&#39;</code> <em>exactly</em> <code>n</code> <em>times on the screen</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> Initially, we have one character &#39;A&#39;.
In step 1, we use Copy All operation.
In step 2, we use Paste operation to get &#39;AA&#39;.
In step 3, we use Paste operation to get &#39;AAA&#39;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 0
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
</ul>

class Solution {
public:
    static constexpr int INF = 1005;
    vector<int> dp = vector<int>(1001, INF);

    int minSteps_dp(int n) {
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j <= i / 2; j++) {
                if (i % j)
                    continue;
                dp[i] = min(dp[i], dp[i - j] + 1);
                dp[i] = min(dp[i], dp[j] + i / j);
            }
        }
        return dp[n];
    }

    int minSteps_bfs(int n) {
        
        queue<pair<int, int>> q; // cur, steps
        int ans = 1003;

        q.push({1, 0});
        for (int k = 2; k <= n; k++)
            q.push({k, k});

        while (!q.empty()) {
            auto qfront = q.front();
            auto& [cur, steps] = qfront;
            q.pop();
            if (cur == n) {
                ans = min(ans, steps);
                continue;
            }
            for (int k = 1; k <= n && (k * cur) <= n; k++) {
                q.push({cur + k * cur, steps + 1 + k});
            }
        }
        return ans;
    }

    int minSteps(int n) {
        return minSteps_bfs(n);
    }
};
73706