跳到主要内容

键盘题库

只有两个键的键盘​

最初记事本上只有一个字符 'A' 。你每次可以对这个记事本进行两种操作：

  • Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
  • Paste（粘贴）：粘贴 上一次 复制的字符。

给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

示例1:

输入：3
输出：3
解释：
最初, 只有一个字符 'A'。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 'AA'。
第 3 步, 使用 Paste 操作来获得 'AAA'。

方案 动态规划​

思路:

  1. 状态定义: dp[i]表示打印i个A的最少操作次数
  2. 状态转移方程: 由于我们只能使用「复制全部」和「粘贴」两种操作，那么要想得到i个A,我们必须首先拥有j个A,使用一次「复制全部」操作，再使用若干次「粘贴」操作得到i个A。因此，这里的j必须是i的因数，「粘贴」操作的使用次数即为i/j-1,我们可以枚举j进行状态转移,则方程为:
  • dp[i]=min(dp[i],dp[j]+i/j)
  • dp[i]=min(dp[i],dp[i/j]+j)
  1. 初始化状态:
  2. 问题答案:

:::details 点击查看代码

function minSteps(n) {
    const dp=new Array(n+1).fill(0);
    for(let i=2;i<=n;i++){
        dp[i]=Infinity;
        for(let j=1;j*j<=i;j++){
            if(i%j==0){
               dp[i]=Math.min(dp[i],dp[j]+i/j); 
               dp[i]=Math.min(dp[i],dp[i/j]+j);
            }
        }
    }
    return dp[n];
};

:::