题目描述：
Initially on a notepad only one character 'A' is present. You can perform two operations on this notepad for each step:
Copy All: You can copy all the characters present on the notepad (partial copy is not allowed).Paste: You can paste the characters which are copied last time.
Given a number n. You have to get exactly n 'A' on the notepad by performing the minimum number of steps permitted. Output the minimum number of steps to get n 'A'.
Example 1:
Input: 3 Output: 3 Explanation: Intitally, we have one character 'A'. In step 1, we use Copy All operation. In step 2, we use Paste operation to get 'AA'. In step 3, we use Paste operation to get 'AAA'.
Note:
- The
nwill be in the range [1, 1000].
题目大意：
记事本中初始有一个字符'A'，提供两种操作：1. 全选 2. 粘贴
给定数字n，求生成n个字符'A'所需的最少操作次数。
解题思路：
动态规划（Dynamic Programming）
dp[n]表示生成n个字符所需的最小操作次数 dp[0, .. , n]初始为∞ dp[0] = dp[1] = 0
状态转移方程：
dp[x] = min(dp[x], dp[y] + x / y) ，y ∈[1, x) 并且 x % y == 0
Python代码：
class Solution(object):
def minSteps(self, n):
"""
:type n: int
:rtype: int
"""
dp = [0x7FFFFFFF] * (n + 1)
dp[0] = dp[1] = 0
for x in range(2, n + 1):
for y in range(1, x):
if x % y == 0:
dp[x] = min(dp[x], dp[y] + x / y)
return dp[n]
本文链接：http://bookshadow.com/weblog/2017/07/30/leetcode-2-keys-keyboard/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
