题目:初始化字符只有一个A,现在有两种操作:1.复制当前所有字符。2.粘贴。使用这两种操作得到n个A字符,求最少的步数。

思路:我是在dp的tag下找到的这个题目,但是我发现最简单的解法应该直接使用贪心算法就可以了。

要得到n个A字符,可以认为最少的步数肯定是通过粘贴最多的字符来得到的,那么反推就能得到最少步数了。

举个例子,如果输入n=12,那么根据贪心的思想,可以认为是先得到6个A,然后进行复制粘贴两步得到,6个A又是通过3个A粘贴得到,3个A需要3步得到,那么总共需要的最少步数是:3(3A) + 2(3A -> 6A)+ 2(6A -> 12A)= 7步。

代码如下(JS实现):

var minSteps = function(n) {
    let sum = 0;
    while (n >= 2) {
        for (let i = 2; i <= n; i++) {
            if (n % i === 0) {
                sum += i;
                n = n / i;
                break;
            }
        }
    }
    
    return sum;
};

 

分类: 算法

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注