题目描述
解题思路
题目大意自不必说,至于说解法,这道题目有想过往动态规划方面去想,但想着想着就被可爱的某婷带偏了,不过最后还竟另辟蹊径,通过对数字本身的研究而解出本题。大致思路如下:
对于n个字符A,如果想要找出最小的复制粘贴步数,为何不从它的因数找起呢?以42为例,42=21*2=7*3*2,也就是说我要先复制初始的一个A,粘贴得到一个A之后,再复制这两个A,粘贴2次得到6个A,再复制这6个A,粘贴6次就可以得到42个A啦,当然关于这理论的证明我暂时无法给出,不过Accept证实我这个想法是ok的。
class Solution {
public:
int minSteps(int n) {
int t = 2;
int a[1000], p = -1;;
while (n != 1) {
while (n % t != 0) {
t++;
}
a[++p] = t;
n = n / t;
}
int result = 0;
for (int i = 0; i <= p; ++i) {
result += a[i];
}
return result;
}
};
运行结果显示
后来又查看了题目解析,重新构思动态规划的方法后发现有异曲同工之妙,即令dp[i]表示要想生成i个字符所需要的步数,初始值dp[0]=dp[1]=0;状态转移方程为dp[i]=min(dp[i],dp[j]+i/j),i>1,j
class Solution {
public:
int minSteps(int n) {
vector
dp(n+1,1000000);
dp[0] = dp[1] = 0;
for(int i=2;i