一、题目描述
最初记事本上只有一个字符 ‘A’ 。
你每次可以对这个记事本进行两种 *** 作:
- Copy All(复制全部):复制这个记事本中的所有字符(不允许仅复制部分字符)。
- Paste(粘贴):粘贴 上一次 复制的字符。
给你一个数字 n ,你需要使用最少的 *** 作次数,在记事本上输出 恰好 n 个 ‘A’ 。
返回能够打印出 n 个 ‘A’ 的最少 *** 作次数。
输入:3
输出:3
解释:
最初, 只有一个字符 'A'。
第 1 步, 使用 Copy All *** 作。
第 2 步, 使用 Paste *** 作来获得 'AA'。
第 3 步, 使用 Paste *** 作来获得 'AAA'。
示例 2:
输入:n = 1
输出:0
二、解题 数学
将n分解为m个数字的乘积, 且m个数字的和最小, 即把一个数分解为n个质数的和, 从小到大的去试探。
class Solution {
public int minSteps(int n) {
if(n == 1){
return 0;
}
int res = 0;
for(int i = 2;i<=n;i++){
while(n%i == 0){
res+=i;
n/=i;
}
}
return res;
}
}
动态规划
-
1、如果n为一个质数,那么结果就是n,因为只能一个个粘贴。
-
2、如果n为一个合数,那么他的结果就是分解因式的结果之和,
- 比如n 为8 ,
- 那么dp[8] = dp[4]+dp[2]; 因为,8 = 4 * 2
dp[4] = dp[2]+dp[2]; 因为,4 = 2 * 2
由于因为2是一个质数,dp[2] = 2; - 于是dp[8] = 6就是我们要求的结果。
- 那么dp[8] = dp[4]+dp[2]; 因为,8 = 4 * 2
- 比如n 为8 ,
class Solution {
public int minSteps(int n) {
if(n == 1){
return 0;
}
//动态规划
int[] dp = new int[n+1];
for(int i = 2;i<=n;i++){
dp[i] = i;
for(int j = 2;j*j<=i;j++){
if(i%j == 0){
dp[i] = dp[j] + dp[i/j];
break;
}
}
}
return dp[n];
}
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)