650_javascript.js

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

// 2021.09.19 每日一题

// 动态规划
/**
 * @param {number} n
 * @return {number}
 */
var minSteps = function (n) {
  let dp = new Array(n + 1);

  dp[1] = 0;
  dp[2] = 2;
  for (let i = 3; i <= n; i++) {
    // 求i的最大公约
    let min = i;
    // 只需要求到 i的一半
    // dp[50] 为例 只需求到 2 - 25 的公约数
    for (let j = 2; j < i / 2; j++) {
      // 有公约数
      // 只要求得其值 如 dp[50] = dp[10 * 5] = dp[2 * 25] = dp[1 * 50]
      // 也就是 dp[10] 有10个A之后 拷贝一次 复制四次  即dp[10] + 5
      // 或  dp[25] 有 25个A之后 拷贝一次 复制一次  即dp[25] + 2
      if (i % j == 0) {
        min = Math.min(min, dp[i / j] + j);
      }
    }
    dp[i] = min;
  }
  return dp[n];
};