650 只有两个键的键盘（递推、数学-分解质因数）

素颜马尾好姑娘i 2022-08-29 06:17 105阅读 0赞

**1. 问题描述：**

最初在一个记事本上只有一个字符 'A'。你每次可以对这个记事本进行两种操作：  
Copy All (复制全部) : 你可以复制这个记事本中的所有字符(部分的复制是不允许的)。  
Paste (粘贴) : 你可以粘贴你上一次复制的字符。  
给定一个数字 n 。你需要使用最少的操作次数，在记事本中打印出恰好 n 个 'A'。输出能够打印出 n 个 'A' 的最少操作次数。

**示例 1:**

输入: 3  
输出: 3  
解释:  
最初, 我们只有一个字符 'A'。  
第 1 步, 我们使用 Copy All 操作。  
第 2 步, 我们使用 Paste 操作来获得 'AA'。  
第 3 步, 我们使用 Paste 操作来获得 'AAA'。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/2-keys-keyboard

**2. 思路分析：**

① 分析题目可以知道构成长度为n的字符串可以有很多种方案，我们需要在所有能够构成长度为n的字符串中找到一个操作次数最少的方案，然后输出这个最少的操作次数。因为需要求解所有方案中最优的那个方案而且长度较长的字符串是由长度较短的字符串的若干次操作构成的所以我们可以使用**递推**求解，根据题目的描述我们可以定义一个一维数组，其中dp\[i\]表示获得i个A的最少操作步数，获得i个A主要有两个步骤，第一个步骤是全选 + 复制操作，第二个步骤是粘贴操作，我们可以枚举上一个步骤中得到的A的数目j，然后当前执行i / j次的粘贴操作那么就可以得到i个A（前提是i能够整除j），所以状态转移方程为dp\[i\] = min(dp\[i\], dp\[j\] + i // j)，使用两层循环枚举即可，第一层循环枚举当前有i个A，第二层循环枚举所有获得i个A的操作方案中操作步数最少的那个。

② 除了使用①中递推的方法还可以使用数学的思路来解决，我们可以先找一下规律，可以发现获得n个A为若干段一次复制多次粘贴操作构成的操作序列，对应序列A的长度为x1x2...xk，反过来n可以分解为若干个数相乘那么就可以构造对应的操作次数，所以他们是一一对应的关系，并且当x为合数的时候一定可以分解为两个大于1的数字相乘，当n = x1x2...xk的操作次数和n = x1x2...xk中的xi分解为pq两个数相乘的时候的操作次数对比：

n = x1x2...xk --> x1 + x2 + ... + xi + ... xk (1)

n = x1x2...xk --> x1 + x2 + ... + p + q + .... xk (2)

可以发现（1) - (2) = xi - p - q = pq - p - q，而(p - 1)(q - 1) = pq - p - q + 1，因为p > 1且q > 1，p,q都为整数所以p >= 2，q >= 2，所以(p - 1)(q - 1) >= 1也即pq >= p + q，pq >= p + q是恒成立的，所以将其中一个数字分解为两个数相乘那么答案是更小的，所以问题就等价于将n = x1x2...xk中的合数质因数分解。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70][]

**3. 代码如下：**

**递推：**

class Solution:
        # dp[i]表示获得i个A的最少操作步数
        def minSteps(self, n: int) -> int:
            # 数组元素最大为1000所以我们定义一开始所有元素值为10 ** 4 
            dp = [10 ** 4] * (n + 1)
            # 初始状态表示1个A的时候最少操作次数
            dp[1] = 0
            for i in range(2, n + 1):
                for j in range(1, i):
                    if i % j == 0:
                        dp[i] = min(dp[i], dp[j] + i // j)
            return dp[n]

**数学：**

class Solution:
        # 质因数分解
        def minSteps(self, n: int) -> int:
            i = 2
            res = 0
            while i * i <= n:
                while n % i == 0:
                    n //= i
                    res += i
                i += 1
            if n > 1: res += n
            return res

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5NDQ1MTY1_size_16_color_FFFFFF_t_70]: /images/20220829/253a912b3e4d48cca97ddf48d0e15454.png