650. 只有两个键的键盘

最初记事本上只有一个字符 ‘A‘ 。你每次可以对这个记事本进行两种操作：

• Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
• Paste（粘贴）：粘贴 上一次 复制的字符。

给你一个数字 n ，你需要使用最少的操作次数，在记事本上输出 恰好 n 个 ‘A‘ 。返回能够打印出 n 个 ‘A‘ 的最少操作次数。

题目链接：650. 只有两个键的键盘 - 力扣（LeetCode） (leetcode-cn.com)

动态规划

思路

• dp[i] 代表得到i个A需要的最小操作次数

• i个A 只可以由整数倍的 j个A 得到，首先copy 1次 ，接着粘贴 (i//j)-1 次

• 动态转移方程 dp[i] = min(dp[i],dp[j]+1+i//j-1) 即 dp[i] = min(dp[i],dp[j]+i//j)

• 最后返回 dp[n]

class Solution:
    def minSteps(self, n: int) -> int:
        if n == 1:
            return 0
        dp = [float(‘inf‘)] * (n+1)
        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[-1]

leetcode650.只有两个键的键盘——leetcode每日一题2021.9.19