只有两个键的键盘

题目

题目来源：力扣（LeetCode）

最初记事本上只有一个字符 ‘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、状态定义
dp[i][j] 表示记事本上当前字符为 i 个，剪切板字符为 j 个时的最少操作数

2、确定递推公式

• 如果 i == j ，说明最后一次操作是 Copy All 操作，那么此时的记事本上的字符数与粘贴板的字符数相等，此时的 dp[i][j] = min(dp[i][x] + 1) ，其中 0 ≤ x < i 。

• 如果 i != j ，说明最后一次操作是 Paste 操作，那么此时粘贴板的字符数量不会发生变化，即有

dp[i][j]=dp[i - j][j] + 1

3、状态初始化
dp[1][0] = 0 表示初始时记事本上只有一个字符，还未做任何操作；
dp[1][1] = 1 表示进行了一次 Copy All 操作。

4、返回值
min(dp[n][x]) ，其中 0 < x < i

代码实现

/**
 * @param {number} n
 * @return {number}
 */
var minSteps = function (n) {
  let dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(Number.MAX_SAFE_INTEGER));
  dp[1][0] = 0;
  dp[1][1] = 1;
  for (let i = 2; i <= n; i++) {
    let min = Number.MAX_SAFE_INTEGER;
    for (let j = 1; j <= i; j++) {
      if (i != j) {
        dp[i][j] = dp[i - j][j] + 1;
        min = Math.min(min, dp[i][j]);
      } else {
        dp[i][j] = min + 1;
      }
    }
  }
  let ans = Number.MAX_SAFE_INTEGER;
  for (let i = 0; i <= n; i++) ans = Math.min(ans, dp[n][i]);
  return ans;
};

优化

观察动态规划的转移方程，不难发现有很多无效的状态，比如：

dp[3][2]，根据转移方程，dp[3][2]=dp[1][2] + 1，而 dp[1][2] 表示当前字符为 1个，剪切板字符数量为 2 个，这明显是不存在的。
dp[5][2]，根据转移方程，dp[5][2]=dp[3][2] + 1，因为 dp[3][2] 是无效的，所以，dp[5][2] 也是无效的。
那么，什么样的状态才是有效的呢？

其实，不难发现，只有当 i % j == 0 的时候，这个状态才是有效的。

因为，只有当 i % j == 0 时，dp[i][j]=dp[i - j][j] 中，dp[i - j] 也才是有效的。

比如，以 dp[9][3] 为例，dp[9][3]=dp[6][3] + 1，而 dp[6][3]=dp[3][3] + 1，而 dp[3][3]=dp[3][1] + 1（因为dp[3][2] 无效，所以，只需要考虑dp[3][1]就可以了），最后 dp[3][1]=dp[2][1] + 1，而 dp[2][1]=dp[1][1] + 1，dp[1][1] 为我们的初始值。

所以，我们可以进一步优化我们的动态规划，当 i%j==0 的时候才计算。

/**
 * @param {number} n
 * @return {number}
 */
var minSteps = function (n) {
  let dp = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(Number.MAX_SAFE_INTEGER));
  dp[1][0] = 0;
  dp[1][1] = 1;
  for (let i = 2; i <= n; i++) {
    let min = Number.MAX_SAFE_INTEGER;
    for (let j = 1; j <= i; j++) {
      if (i % j == 0) {
        if (i != j) {
          dp[i][j] = dp[i - j][j] + 1;
          min = Math.min(min, dp[i][j]);
        } else {
          dp[i][j] = min + 1;
        }
      }
    }
  }
  let ans = Number.MAX_SAFE_INTEGER;
  for (let i = 0; i <= n; i++) ans = Math.min(ans, dp[n][i]);
  return ans;
};