电脑配件经营网站的建设论文,seo 重庆,网站建设一站式服务公司,wordpress 展示类主题650. 只有两个键的键盘
最初记事本上只有一个字符 A 。你每次可以对这个记事本进行两种操作#xff1a;
Copy All#xff08;复制全部#xff09;#xff1a;复制这个记事本中的所有字符#xff08;不允许仅复制部分字符#xff09;。Paste#xff08;粘贴#xff09…650. 只有两个键的键盘
最初记事本上只有一个字符 A 。你每次可以对这个记事本进行两种操作
Copy All复制全部复制这个记事本中的所有字符不允许仅复制部分字符。Paste粘贴粘贴 上一次 复制的字符。
给你一个数字 n 你需要使用最少的操作次数在记事本上输出 恰好 n 个 A 。返回能够打印出 n 个 A 的最少操作次数。
示例 1 输入3 输出3 解释 最初, 只有一个字符 ‘A’。 第 1 步, 使用 Copy All 操作。 第 2 步, 使用 Paste 操作来获得 ‘AA’。 第 3 步, 使用 Paste 操作来获得 ‘AAA’。 示例 2 输入n 1 输出0 提示
1 n 1000
思路(动态规划)
动态规划问题最重要的是先确定一共有哪些状态然后分析每种状态的关系从而确定 状态转移方程。
第一步确定所有的状态
随意看其中的一步就两种状态不是先复制记事本字符的全部再粘贴就是粘贴已经在粘贴板上的
1、复制再粘贴2、粘贴
第二步分析每种状态的关系确定状态转移方程 1、复制再粘贴只有当前记事本上的字符数是目标数的因子即能整除目标数此时才能复制完再粘贴进而能得到目标数 复制一次粘贴一次此时的操作数总数2即总操作数为: ans2ans 2ans2粘贴板上字符的长度为复制前记事本上的字符数即粘贴板上字符数为pastenumpaste numpastenum粘贴后记事本上的字符数要加上粘贴的字符数即完成一次复制粘贴记事本上的字符数为numpastenum pastenumpaste 2、粘贴此时记事本上的字符数不能整除****目标数则复制当前记事本上的长度一定到达不了目标数则 只能粘贴已经在粘贴板上的字符 只粘贴一次总操作数1即总操作数为: ans1ans 1ans1粘贴后记事本上的字符数要加上粘贴的字符数即完成一次粘贴记事本上的字符数为numpastenum pastenumpaste
代码(Java)
public class MInSteps {public static void main(String[] args) {// TODO Auto-generated method stubint n 3;System.out.println(minSteps(n));}public static int minSteps(int n) {if(n 1) {return 0;}int num 2;//至少两个字符,从两个字符开始int ans 2;//总操作数,两个字符时已经复制粘贴各一次且此时粘贴板上有一个字符了int paste 1; //复制板上的字符数while(num n) {if(n % num 0) {ans 2; //复制 粘贴paste num;}else {ans 1; //粘贴}num paste;//当前数粘贴板上字符数}return ans;}
}
运行结果 力扣提交
复杂度分析
时间复杂度O(n)O(n)O(n)最坏的情况n是质数一次只能粘贴一次要粘贴n次。空间复杂度O(1)O(1)O(1)只需要常数级别的空间。
注仅供学习参考 如有不足欢迎指正
题目来源力扣。
