每日一题_650. 只有两个键的键盘
题目：
题意分析：
题目的意思是说，初始情况下只有一个A的情况下，如何能够得到n个A，其中能用的操作只有复制和粘贴，并且粘贴只能粘贴最近一次copy的内容。
动态规划：
首先，我们可以先尝试一些较小的数，体会一下其中的规律，我尝试了一下11以内，然后首先发现所有的素数的操作次数都是自身的n，然后比如8，我们只需要在有4个A的时候，复制一下再粘贴，那么就能得到8个A，为了方便我们的描述，我们设dp[i]表示得到i个A所需要的操作次数，那么
d
p
[
8
]
=
d
p
[
4
]
+
2
dp[8] = dp[4] + 2
dp[8]=dp[4]+2，8是偶数，我们再看9，我们在得到3个A的时候，复制一次，再粘贴两次就得到了9个A，即
d
p
[
9
]
=
d
p
[
3
]
+
3
dp[9] = dp[3] + 3
dp[9]=dp[3]+3，从这里，我们其实就可以窥出一些端倪了，首先得到 i 个A和得到j(j < i)个A有关，也就是说具有最优子结构，因此使用动态规划。但是j的选取我们并不知道，但是必须满足能整除i，即 i % j = 0。在这个的前提下，取选择最小的一个，因此算法如下：
dp[i]表示得到i个A需要的最小的操作次数，状态转移方程：
f
[
i
]
=
min
j
∣
i
(
f
[
j
]
+
i
j
)
f[i] = \min\limits_{j|i} ( f[j] + \frac{i}{j} )
f[i]=j∣imin(f[j]+ji)
代码：
class Solution {
public:
int minSteps(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[1] = 0;
for (int i = 2; i <= n; i ++)
for (int j = 1; j < i; j ++)
if ( i % j == 0)
dp[i] = min(dp[i], dp[j] + i/j);
return dp[n];
}
};
数学：
从第一个方法的转移方程中，我们得到n个A，实际上我们是把j个A重复复制了i/j遍，也就是 n = j * (n / j)，虽然这么写相当于废话，但仔细看转移方程：
d
p
[
n
]
=
d
p
[
j
]
+
n
/
j
dp[n] = dp[j] + n/j
dp[n]=dp[j]+n/j，因此实际上我们把n进行了质因数分解，因为递归求解j也是这么做的，因此我们来换个思路，刚刚从n往回看，我们从头开始看：
如果我们将 1 次 Copy All + x 次 Paste 看做一次“动作”的话。
那么一次“动作”所产生的效果就是将原来的字符串变为原来的
x
+
1
x + 1
x+1倍。
最终的得到n个A的最小操作次数方案可以等价以下操作流程：
- 起始对长度为 1 的记事本字符进行 1 次 C o p y A l l + k 1 − 1 Copy All + k_1 - 1 CopyAll+k1−1次 Paste 操作（消耗次数为 k 1 k_1 k1，得到长度为 k 1 k_1 k1的记事本长度）；
- 对长度为为
k
1
k_1
k1 的记事本字符进行 1 次
C
o
p
y
A
l
l
+
k
2
−
1
Copy All + k_2 - 1
CopyAll+k2−1 次 Paste 操作（消耗次数为
k
1
+
k
2
k_1 + k_2
k1+k2 ，得到长度为
k
1
∗
k
2
k_1 * k_2
k1∗k2的记事本长度）
… …
最终经过 k 次“动作”之后，得到长度为 n 个A，即有：
n
=
k
1
∗
k
2
∗
k
3
∗
.
.
.
∗
k
x
n = k_1 *k_2 *k_3 *... * k_x
n=k1∗k2∗k3∗...∗kx
因此问题转化为，
K
=
∑
k
i
K = \sum k_i
K=∑ki
求
K
K
K的最小值。
对于
k
i
k_i
ki而言 ，如果是一个合数，那么
k
i
=
a
∗
b
k_i = a * b
ki=a∗b，很容易证明
a
∗
b
>
a
+
b
(
a
>
1
,
b
>
1
)
a * b > a + b \quad(a > 1, b > 1)
a∗b>a+b(a>1,b>1)
因此
K
K
K 要取得最小，只需要对
k
i
k_i
ki 不断分解，直至不能分解，也就是素数了，这也就是为什么我们一开始尝试看出来的质数的操作次数都是自身n。
因此问题转化为对n进行质因数分解，然后将所有的质因数求和就行了。
代码：
class Solution {
public:
int minSteps(int n) {
int ans = 0;
for (int i = 2; i * i <= n; i ++)
while (n % i == 0)
{
ans += i;
n /= i;
}
if (n != 1) ans += n;
return ans;
}
};