阅读 51

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

650. 只有两个键的键盘

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

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

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

题目链接:

动态规划

思路
  • 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]

原文:https://www.cnblogs.com/waitting975/p/15311737.html

文章分类
代码人生
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐