【每日一題】650. 隻有兩個鍵的鍵盤

最初記事本上隻有一個字元 ‘A’ 。你每次可以對這個記事本進行兩種操作：

Copy All（複制全部）：複制這個記事本中的所有字元（不允許僅複制部分字元）。

Paste（粘貼）：粘貼 上一次 複制的字元。

給你一個數字 n ，你需要使用最少的操作次數，在記事本上輸出 恰好 n 個 ‘A’ 。傳回能夠列印出 n 個 ‘A’ 的最少操作次數。

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/2-keys-keyboard

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

示例 1：

輸入：3
輸出：3
解釋：
最初, 隻有一個字元 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作來獲得 'AA'。
第 3 步, 使用 Paste 操作來獲得 'AAA'。

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/2-keys-keyboard
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
           

示例 2：

輸入：n = 1
輸出：0
           

思路：n>1時 其實就是将n分解為m個數字的乘積 且m個數字的和最小 即把一個數分解為n個質數的和 從小到大的去試探。

舉例子：

代碼：

//一個一個去嘗試
class Solution {
public:
    int minSteps(int n) {
        int res = 0;
        for (int i = 2; i <=n; ++i) {
            while (n % i == 0) {
                res += i;
                n /= i;
            }
        }
        return res;
    }
};

//20 
//20 = 5*2*2