650. 只有两个键的键盘

650. 只有两个键的键盘,第1张


一、题目描述

最初记事本上只有一个字符 ‘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

二、解题 数学

将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就是我们要求的结果。


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];
    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/565158.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-06
下一篇 2022-04-06

发表评论

登录后才能评论

评论列表(0条)

保存