650. 两键键盘
内容提要
这篇文章介绍了一个问题：在记事本上有一个字符'A'，每一步可以进行两种操作：复制全部字符或粘贴上一次复制的字符。给定一个整数n，返回得到n个字符'A'所需的最小操作次数。使用动态规划的方法解决这个问题，通过一个dp数组记录得到i个字符所需的最小操作次数。最后返回dp[n]。
延伸解读
动态规划解法的核心思路
文章采用动态规划，定义dp[i]为得到i个'A'所需的最小操作次数。初始化dp[1]=0，因为初始已有一个'A'。对于每个i从2到n，遍历其所有因子d，若i能被d整除，则dp[i]可由dp[d]加上将d个'A'扩展为i个'A'的操作数得到。这种基于因子的状态转移，本质上是将问题分解为更小的子问题，避免重复计算。
因子枚举与操作次数的关系
在状态转移中，若i能被d整除，则从d个'A'扩展到i个'A'需要先复制全部d个'A'，再粘贴(i/d - 1)次，总操作数为1 + (i/d - 1) = i/d。因此dp[i] = min(dp[i], dp[d] + i/d)。文章通过枚举所有因子d来更新dp[i]，确保找到最小操作次数。这一关系揭示了操作次数与因子分解之间的内在联系。
示例验证与边界情况
文章给出了多个示例：n=3时输出3，n=1时输出0，n=10时输出7，n=24时输出9。这些结果与动态规划的计算一致。特别地，n=1时无需任何操作，直接返回0。对于n=24，最优策略可能是先得到6个'A'（操作5次），再复制粘贴3次得到24个'A'（操作4次），总计9次。这验证了因子分解思路的有效性。
Q&A
如何在记事本上得到n个字符'A'?
可以通过复制全部字符和粘贴上一次复制的字符来实现。
动态规划如何用于解决这个问题?
使用dp数组记录得到i个字符所需的最小操作次数，通过检查每个字符数的因子来更新。
得到一个字符'A'需要多少操作?
得到一个'A'不需要任何操作，因此dp[1] = 0。
如果n=10，最小操作次数是多少?
对于n=10，最小操作次数是7。
如何计算得到n个字符'A'的最小操作次数?
初始化dp数组，遍历从2到n的每个数，检查其因子并更新dp值。
这个问题的最大限制是什么?
问题的限制是1 <= n <= 1000。
