IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> leetcode 650. 2 Keys Keyboard 只有两个键的键盘(中等) -> 正文阅读

[数据结构与算法]leetcode 650. 2 Keys Keyboard 只有两个键的键盘(中等)

一、题目大意

标签: 动态规划

https://leetcode.cn/problems/2-keys-keyboard

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

Copy All(复制全部):复制这个记事本中的所有字符(不允许仅复制部分字符)。
Paste(粘贴):粘贴 上一次 复制的字符。
给你一个数字?n ,你需要使用最少的操作次数,在记事本上输出 恰好?n?个 ‘A’ 。返回能够打印出?n?个 ‘A’ 的最少操作次数。

示例 1:

输入:3
输出:3
解释:
最初, 只有一个字符 ‘A’。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 ‘AA’。
第 3 步, 使用 Paste 操作来获得 ‘AAA’。

示例 2:

输入:n = 1
输出:0

提示:

  • 1 <= n <= 1000

二、解题思路

还是动态规划,这里需要乘除法来计算位置,因为粘贴操作是位数增加的。我们使用一个一维数组dp,其中位置i表示延展到长度i的最少操作次数。对于每个位置j,如果j可以被i整除,那么长度i就可以由长度j操作得到,其操作次数等价于把一个长度为1的A延展到长度为i/j。因此我们可以得到递推公式dp[i] = dp[j] + dp[i/j]。

三、解题方法

3.1 Java实现

public class Solution {
    public int minSteps(int n) {
        int[] dp = new int[n + 1];
        int h = n * n;
        for (int i = 2; i <= n; i++) {
            dp[i] = i;
            for (int j = 2; j <= h; j++) {
                if (i % j == 0) {
                    dp[i] = dp[j] + dp[i / j];
                    break;
                }
            }
        }
        return dp[n];
    }
}

四、总结小记

  • 2022/7/2 期待7月11号
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-07-05 23:40:24  更:2022-07-05 23:40:53 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/25 23:51:49-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码