您现在的位置是:首页 > 正文

651. 4键键盘(动态规划)

2024-04-01 03:56:41阅读 7

651. 4键键盘

题目

假设你有一个特殊的键盘包含下面的按键:

Key 1: (A):在屏幕上打印一个 'A'。

Key 2: (Ctrl-A):选中整个屏幕。

Key 3: (Ctrl-C):复制选中区域到缓冲区。

Key 4: (Ctrl-V):将缓冲区内容输出到上次输入的结束位置,并显示在屏幕上。

现在,你只可以按键 N 次(使用上述四种按键),请问屏幕上最多可以显示几个 'A’呢?

样例 1:
输入: N = 3
输出: 3
解释: 
我们最多可以在屏幕上显示三个'A'通过如下顺序按键:
A, A, A
 
样例 2:
输入: N = 7
输出: 9
解释: 
我们最多可以在屏幕上显示九个'A'通过如下顺序按键:
A, A, A, Ctrl A, Ctrl C, Ctrl V, Ctrl V

注释:
1 <= N <= 50
结果不会超过 32 位有符号整数范围。

解题思路

①确定状态,也就是变化的量,本题应该有三个状态,屏幕上A的数量、剪贴板中A的数量,按键次数N。这题为了dp数组的简单,就选择一个状态, 按键次数N

②其实我们的最优按键序列只有两种情况:

  1. 要么一直按A
  2. 要么A,A,…,C-A,C-C,C-V…(当N比较大的时候)

用一句话来概括就是,最后一次要么按A,要么按C-V。这就是两种情况了

③定义dp[ ]:dp[N] 代表N次按键后A的数量

④对于按A,统计A的个数好说,但是对于按C-V,我们就需要用一个变量j来记录一下上一次按C-A,C-C的时机。

⑤现在大题思路都出来了,只需要记录按A键的A个数,然后遍历C-A,C-C的时机,在该时机下按C-V后A的个数,选取二者较大的那个即可。

看个图就明白了
在这里插入图片描述

这里解释一下按下C-V后A的个数dp[j - 2] * (i - j + 1)
按下C-V后,就是把剪贴板中的A的个数dp[j - 2]乘以按下C-V的次数i-j
但是为啥要加一个1呢?
因为我们求出的dp[j - 2]*(i-j)只是按下C-V后出现的A,而屏幕上的A的个数是按下C-V后的A的个数dp[j - 2]*(i-j),加上屏幕上原来存在的A的个数dp[j-2],才是屏幕上最终的A的数量

代码

 class solution{

    public int maxA(int N) {
        //dp[N] 代表N次按键后A的数量
        int dp[] = new int[N + 1];//长度为N+1是为了填入base case dp[0]=0
        //base case
        dp[0] = 0;

        for (int i = 1; i <= N; i++) {
            //此次按的是A键,那么产生的A就是上次的A数量加1
            dp[i] = dp[i - 1] + 1;
            /*用j来保存上一次按完C-A,C-C的时机,此时剪贴板中A的个数就是dp[j-2]
            因为  比如按键顺序如下A,A,A,C-A,C-C。j=5,但是A的数量为dp[j-2]=dp[3]。

            下面j从2开始也是同理。因为要有dp[j-2]所以j必须大于等于2才会让j-2始终大于等于0
            也可以理解为就是第一次按键就是C-A,C-C那也要两次按键。
             */
            for (int j = 2; j < i; j++) {
                //选出按A键,和按C-A,C-C后再按C-V键那个A数量多。
                dp[i] = Math.max(dp[i], dp[j - 2] * (i - j + 1));
            }
        }

        return dp[N];
    }
}

网站文章

  • 深度解析ngx_command_t结构

    因为HTTP框架可以使用预设的14种方法自动 地将解析出的配置项写入HTTP模块代码定义的结构体中,但HTTP模块中可能会定义3个结 构体,分别用于存储main、srv、loc级别的配置项(对应于cr...

    2024-04-01 03:56:35
  • 性能调优11:查询统计

    数据库引擎的工作流程可以归纳为接收请求、执行请求和返回结果。数据库引擎每接收到一个新的查询请求(Query Request),查询优化器就会执行以下工作流程:编译请求:对TSQL语句进行语法解析,编译请求,生成TSQL语句表示的逻辑结构。查询优化:根据TSQL语句的逻辑结构,生成多个预估的执行方案,并根据统计信息,评估每个预估方案的开销,选择开销最低的方案作为最优方案。执...

    2024-04-01 03:55:54
  • Linux Shell 定时删除某几天前文件夹下文件

    脚本 #!/bin/sh echo &#39;清除文件开始&#39;; find /tmp/email -mtime +1 -name &quot;*.*&quot; -exec rm -Rf {} ...

    2024-04-01 03:55:46
  • 前后端分离单点登录

    前后端分离单点登录

    单点登录基于 Apereo CAS实现,不是此次记录的重点。 登陆过程中,需要重定向至CAS Server,前端Vue+axios,需要从单页面跳转至login页面,后端如果使用response.sendRedirect(),返回302,axios并不能拦截到302,浏览器会自动跳转,就会出问题。 解决: 后端判断请求是否是axios(Ajax)请求,如果是,不返回302,约定一个返回码...

    2024-04-01 03:55:38
  • Harbor仓库的管理

    Harbor仓库的管理

    2024-04-01 03:54:58
  • APT(Advanced Persistent Threat高级持续性威胁)——网络安全

    APT(Advanced Persistent Threat高级持续性威胁)——网络安全

    网络安全APT(Advanced Persistent Threat高级持续性威胁)是一种复杂的网络攻击,旨在长期潜伏在目标网络中,有组织的黑客或攻击者利用高级技术手段对目标系统进行持续的渗透和监视,以获取敏感信息、窃取数据或进行其他恶意攻击活动。下面是一些关于网络安全有关APT的介绍:

    2024-04-01 03:54:52
  • Lucene .NET 全文检索

    Lucene .NET 全文检索

    近期做项目中有用到过Lucene,那个模块是由一位前端大神负责的,空闲时间我也做了个关于Lucene做全文检索的Demo,记录下来,方便以后学习。 关于Lucene的原理,网上有长篇大论的文章,有兴趣的话可以去阅读,再次我就直奔主题,在代码中分析其原理。 1、创建索引(此处我用的是盘古分词) 注:在后台代码的第一行上加上 #definenotes这样一行代码,目的是可以用外侧代码的#if,

    2024-04-01 03:54:44
  • mysql捕获 分析和优化sql

    mysql捕获 分析和优化sql

    2024-04-01 03:54:02
  • 基于PO和单例设计模式用python+selenium进行ui自动化框架设计【多测师_王sir】

    基于PO和单例设计模式用python+selenium进行ui自动化框架设计【多测师_王sir】

    一)框架目录的结构二)config包当中的config.ini文件主要是用来存项目的绝对路径,是为了后续跑用例和生成测试报告做准备然后目前的配置文件大都会用yaml,ini,excel,还有.py也就是python文件来进行管理这里用的是ini文件。三)config包当中的globalconfig文件主要是用来生成项目的路径,测试用例,测试报告的路径其中调用了ReadConfigIni这...

    2024-04-01 03:53:56
  • 将字节转换成十六进制字符串

    /* * 将字节数组转换为十六进制字符串 * * @param byteArray * @return */ private static String byteToStr(byte[] byteArray) { String strDigest = &quot;&quot;; for (int i = 0

    2024-04-01 03:53:49