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

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

上一篇:Mysql错误:Ignoring query to other database解决方法


下一篇:android9.0系统适配遇到的问题