650.两个键的键盘

链接：650.两个键的键盘
难度：Medium
标签：数学、动态规划
简介：给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 'A' 。返回能够打印出 n 个 'A' 的最少操作次数。

题解 1 - javascript

• 编辑时间：2021-09-19
• 执行用时：76ms
• 内存消耗：40MB
• 编程语言：javascript
• 解法介绍：动态规划。

function minSteps(n: number): number {
  if (n === 1) return 0;
  const dp = new Array(n + 1).fill(0);
  for (let num = 2; num <= n; num++) {
    if (num % 2 === 0) {
      dp[num] = dp[num / 2] + 2;
      continue;
    }
    for (let i = num - 1; i >= 2; i--) {
      if (num % i === 0) {
        dp[num] = dp[i] + num / i;
        break;
      }
    }
    if (dp[num] === 0) dp[num] = num;
  }
  return dp[n];
}