<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>

#if 1
class Solution {
public:
    int minSteps(int n) {
        auto dp = vector(n, vector<int>(n / 2 + 1, -1));

        if (n == 1) {
            return 0;
        }
        auto dfs = [&](auto&& dfs, int counts, int paste) -> int {
            if (counts == n) {
                return 0;
            }
            if (counts > n) {
                return 1000;
            }
            if (dp[counts][paste] != -1) {
                return dp[counts][paste];
            }
            // paste
            int res1 = 1 + dfs(dfs, counts + paste, paste);
            // copy & paste
            int res2 = 2 + dfs(dfs, counts * 2, counts);
            return dp[counts][paste] = min(res1, res2);
        };
        return 1 + dfs(dfs, 1, 1);
    }
};

// neetcode
// 想法也是 recursion + DP
// 不過分支切成 1. paste 2. copy + paste
// 這樣也可以避免陷入無限迴圈 (只copy 或者 paste 0 的狀況)
// 為了做到 paste 一開始就有1 
// 所以一開始遞迴入口就要先 +1 steps

// 另外這樣寫要特判 n == 1
// 大小的話 可以開 n * n/2
// 因為 paste代表著複製的長度
// 如果超過 n/2 意味著下一次貼上一定會超過 n 
// 我們最糟的情況下只需要剛剛好一半的長度就好

// time: O(n^2)
// space: O(n^2)
#endif

#if 0
class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n + 1, 1000);
        dp[1] = 0;
        for (int i = 2; i <= n; ++i) {
            for (int x = 1; x <= i / 2; ++x) {
                if (i % x == 0) {
                    dp[i] = min(dp[i], dp[x] + (i / x));
                }
            }
        }
        return dp[n];
    }
};

// neetcode
// 另一種想法
// 假想我們一開始是從1個字母出發 要貼上幾次才會到 n
// 1 -> ? -> n
// 答案是 n/1 次
// 那假設存在一個最終的複製長度 x
// 我們可以一直貼上 x 讓他走到 n
// 又如果要能複製x的話 我們的長度最少也需要x 
// 也就是 1 ... x -> ? steps -> n
// 那回到一開始的說法 如果從x出發 要貼上幾次才會到 n 
// 也就是 n/x 次
// 基於這樣的觀點來思考
// 我們可以用子問題動態規劃的方式去思考
// dp[n] = dp[x] + n/x

// 接著討論實際寫code的時候
// 1 -> ? -> i
// 我們如果要枚舉 x 那麼 x 必須被 i 整除, 而且如果 x 超過 i / 2 就沒意義(太大了)

// time: O(n^2)
// space: O(n)
#endif

#if 0
class Solution {
public:
    int minSteps(int n) {
        auto dp = vector(n, vector<int>(n, -1));

        auto dfs = [&](auto&& dfs, int counts, int paste) -> int {
            if (counts == 0) {
                return 0;
            }
            if (counts < 0) {
                return 1000;
            }
            if (dp[counts][paste] != -1) {
                return dp[counts][paste];
            }
            int res1 = 1000;
            if (n - counts != paste) {  
                res1 = 1 + dfs(dfs, counts, n - counts);
            }
            int res2 = 1000;
            if (paste != 0) {
                res2 = 1 + dfs(dfs, counts - paste, paste);
            }
            return dp[counts][paste] = min(res1, res2);
        };
        return dfs(dfs, n - 1, 0);
    }
};

// 你在打鍵盤
// 螢幕上已經有一個英文字母 'A'
// 現在有兩個操作 1. 複製所有字 2. 貼上
// 問你最少的操作次數 使得能夠拿到剛好 n 個 'A' 
// ===

// DP 吧
// 因為每次就兩個選擇
// 1. 複製
// 2. 貼上

// 要怎麼 DP?
// 例如說 要拿到 n 個字母
// 一開始已經有 1 個字母了
// 所以問 要怎麼拿到 n - 1 個字母
// 選擇 1. 複製 => 用一個參數表示複製了多少字母
// 例如 => 1 + dfs(dfs, i, n - i);
// 2. 貼上
// => 1 + dfs(dfs, i - paste, paste);
// 邊界條件就 如果 i == 0 return 0
// 應該就這兩個選擇取 min 就好了?
// dp cache 1000*1000 

// 不過不能一直copy 不然他不會往下遞迴
// 所以要規定 如果 paste 跟 n - i 不同 這時候才能copy
// 意思是如果當前字串長度和複製的長度不同 才能copy
// 不然一直 copy 就不會往下遞迴

// 一開始 paste 是 0 這部分也要同樣的處理一下

// time: O(n^2)
// space: O(n^2)
#endif

#if 0
class Solution {
public:
    int minSteps(int n) {
        auto dp = vector(n, vector<int>(n, 1000));
        dp[0][0] = 0;
        for (int counts = 1; counts < n; ++counts) {
            for (int paste = n - 1; paste >= 0; --paste) {
                dp[0][paste] = 0;
                int res1 = 1000;
                if (n - counts != paste) {  
                    res1 = 1 + dp[counts][n - counts];
                }
                int res2 = 1000;
                if (paste != 0 && counts >= paste) {
                    res2 = 1 + dp[counts - paste][paste];
                }
                dp[counts][paste] = min(res1, res2);
            }
        }
        return dp[n - 1][0];
    }
};

// button-up
// i 從 1 開始, 因為 i = 0 就是答案 可以直接回傳 0
// counts 倒序走訪 因為top-down 是從 0 開始出發
// dp[0][x] = 0 => 因為不管有沒有copy 只要 i = 0 答案就是 0

// time: O(n^2)
// space: O(n^2)
#endif
86840