2022年蓝桥杯省赛软件类C/C++B组----积木画

想借着这一个题回顾一下动态规划问题的基本解法,让解题方法清晰有条理,希望更多的人可以更轻松的理解动态规划!

目录

【题目】

【本题解题思路】

【DP模版】

总体方针:

具体解题时的套路:


 【题目】

 

  【本题解题思路】

———类似题目:覆盖墙壁 - 洛谷(很多经典题解在里面)

1、确定子状态:

我最终要求解的是:用两种类型的积木将2 x n的画卷填满时有着多少种组合方案。(围绕最终要求解的问题确定子问题)

所以子问题应该是在长度为n的情况下有多少种解法。

所以用一维数组dp[i] 存储长度为i 时的方案数。

2、确定转移的边界情况和初始状态:

这里先正着推,已知n=3时dp[3]=5,那么就可以先明确n=1,n=2时对应的dp[i],即dp[1]=1,dp[2]=2;

然后发现没有什么明显的规律呢,那就再倒着来

3、确定状态转移方式:

为了方便表述,设画卷长度为len;

我想知道画卷长度为len=n时的值,那么我就找他的上一层 len=n-1时的状态,看看有没有什么关联。为了形成填满画卷的状态,我的最后一块位置可以怎么摆放积木呢,从积木的两种类型出发,发现他可以形成四种状态。这里用分类的思想将所有的选择罗列出来,找规律。

如图所示,最后一次有如下选择:

(1)最后一次选竖着的I ,那么dp[n]=dp[n-1]。

因为最后一位固定好了就这一种选择,即1*dp[n-1]。如图1;

(2)最后一次选横着的I ,那么为了填补上画卷,第二行也只能选横着的I 这两个横着的I作为一个整体是一种填补画卷的方式。此时dp[n]=dp[n-2];

如图2所示。

前两种状态都很明显,但是如果选用L形的怎么罗列呢:

(3)L型垂直翻转前后算两种状态,如图3、4.  下面仅根据其中的一种情况来讨论,最后因为翻转所有的结果×2 即可。

A.可以用两个L形成长度为3的整体来填补画卷,dp[n]=dp[n-3],如图5;

B.采用两个L和一个横着的I的方式形成一个整体作为一种方法填补,dp[n]=dp[n-4],如图6;

C.同上,还可以采用在两侧两个L中间包裹多个横着的I的方式来填补,每多一个横着的I相当于这个用于填补的图像整体的长度+1。所以类推得到dp[n]=dp[n-5],dp[n-6],...  如图7;

综上所述,形成填满画卷的前一个整体的状态可以采用如上这些方式,所以他的方案总数就有:

dp[n]=dp[n-1]+dp[n-2]+2*(dp[n-3]+dp[n-4]+...dp[0]);

假如用前缀和sum[n]表示前n个长度的方案总和,dp[n]=sum[n-1]+sum[n-3];

但是我这里只求了n=1---3的情况,n=4时情况虽然有点复杂,但是也还是不好求(哈哈)。

所以有没有什么化简的方式呢,大家记不记得高考时第一个大题考的数组的性质,这里就可以用来变换公式;

dp[n]=sum[n-1]+sum[n-3];

dp[n-1]=sum[n-2]+sum[n-4];

上下相减发现  dp[n]-dp[n-1]=dp[n-1]+dp[n-3];

所以,dp[n]=2*dp[n-1]+dp[n-3]   

这就把递推公式推出来了,完美撒花!

【DP模版】

总体方针:

凡是动态规划问题,可以从以下三个角度考虑,确定求解问题的基本思路:

(有时是二维问题或者多维问题时可以考虑用二维或者多维数组)

动态规划问题具有两个性质:

(1)无后效性:每个子问题的解都是基于之前子问题的解,而不受后续子问题解的影响。这意味着我们可以独立地解决每个子问题,然后将这些解组合起来形成一个最优解。即当前状态的解只受此状态之前(就是过去的状态)的影响,一经确定,未来的状态不影响当前状态的结果。

(换成人话就是,当前状态的结果是由之前状态形成的,一旦确定,后续的状态对他没有影响)

(2)子问题重叠性:每个子问题之间类似于嵌套的关系,我想求这个子问题,就必须先解决比他规模更小的、具有同样规律的子问题。

具体解题时的套路:

1、按照题目的求解问题,确定子问题是什么,把存储每个子问题的数据结构定义出来;

2、根据题目中给的信息,自己推理、枚举出来所有的可以获得的关于解的信息,看看是否存在什么规律。这里推倒的方式往往是从边界开始往前推导,观察前后状态之间的联系。或者是从初始状态向后推导,找规律。


 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/546624.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Python判断节假日的几种方式,你学废了吗?

最近在推进信息安全巡检的工作,按公司制度要求和信息安全标准,要求按时对硬件设备、网络、机房、应用系统、数据库等等做巡检工作。为了保证达到信息安全的目标,要求在每周四和节假日的前一天对各类设备和系统进行巡检。 1、使用holidays库判…

zookeeper分布式应用程序协调服务+消息中间件kafka分布式数据处理平台

一、zookeeper基本介绍 1.1 zookeeper的概念 Zookeeper是一个开源的分布式的,为分布式框架提供协调服务的Apache项目。 是Hadoop和Hbase的重要组件。它是一个为分布式应用提供一致性服务的软件,提供的功能包括:配置维护、域名服务、…

python小游戏

这些游戏你玩过几个&#xff1f; 1.贪吃蛇2.吃豆人3.加农炮4.四子棋5. Fly Bird<font color #f3704ab>6.记忆&#xff1a;数字对拼图游戏&#xff08;欢迎挑战&#xff01;用时&#xff1a;2min&#xff09;7.乒乓球8.上课划水必备-井字游戏&#xff08;我敢说100%的人都…

代码随想录算法训练营第二十七天|39.组合总和、40.组合总和II、131.分割回文串

39.组合总和 思路&#xff1a; 本题和77.组合 &#xff0c;216.组合总和III的区别是&#xff1a;本题没有数量要求&#xff0c;可以无限重复&#xff0c;但是有总和的限制&#xff0c;所以间接的也是有个数的限制。 本题搜索的过程抽象成树形结构如下&#xff1a; 注意图中叶…

《HF经理》:二认知误区

一、管理者掌握重要权力&#xff1a; 二、全力来自管理者的职位&#xff1a; 三、管理者必须控制自己的直接下属&#xff1a; 对策&#xff1a;展示自己的品质&#xff0c;能力和影响力 四、管理者必须建立良好的个人关系&#xff1a; 五、管理这必须确保一切运行正常&…

【爬虫开发】爬虫从0到1全知识md笔记第5篇:Selenium课程概要,selenium的其它使用方法【附代码文档】

爬虫开发从0到1全知识教程完整教程&#xff08;附代码资料&#xff09;主要内容讲述&#xff1a;爬虫课程概要&#xff0c;爬虫基础爬虫概述,,http协议复习。requests模块&#xff0c;requests模块1. requests模块介绍,2. response响应对象,3. requests模块发送请求,4. request…

分享2024 golang学习路线

写在前面 Go语言&#xff08;也称为Golang&#xff09;是Google开发的一种静态强类型、编译型语言&#xff0c;它具有简洁、快速、安全、并发等特点&#xff0c;尤其适合构建大型软件、微服务架构和云平台服务。Go的学习曲线相对平缓&#xff0c;社区活跃&#xff0c;是现代编…

韩顺平 | 零基础快速学Python(16) 文件处理

文件 输入与输出 输入&#xff1a;数据从数据源(文件)到程序(内存)&#xff1b; 输出&#xff1a;数据从程序(内存)到数据源(文件)。 #mermaid-svg-06PG6JZq4jJMV1oH {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-sv…

五、LoadBalancer负载均衡服务调用

一、Ribbon目前也进入维护模式 1、是什么 Spring Cloud Ribbon是基于Netflix Ribbon实现的一套客户端负载均衡的工具。 简单的说&#xff0c;Ribbon是Netflix发布的开源项目&#xff0c;主要功能是提供客户端的软件负载均衡算法和服务调用。Ribbon客户端组件提供一系列完善的…

掌握CRM+邮箱技巧:销售速度与客户信任双丰收

在千行百业都在谈提效的今天&#xff0c;如果您的销售团队效率较低&#xff0c;恐怕很难过好2024。销售团队提效是个大话题&#xff0c;总的说来就是销售团队需要在正确的时间做正确的事。如何做到&#xff1f;自然要借助CRM工具。过去我们也讲了不少CRM如何辅助销售团队提效的…

Playwright已经是目前最好的测试自动化工具了吗?

作者观点&#xff1a;很长时间以来&#xff0c;Selenium是QA工程师寻求测试自动化解决方案的首选测试框架。它能够测试任何浏览器&#xff08;这在IE浏览器的统治时期尤其重要&#xff09;和任何平台。然而&#xff0c;现在看来&#xff0c;那个时代已经过去了。 今天&#xf…

Python机器学习实战教程

一、引言 机器学习是人工智能的一个子集&#xff0c;它使用算法来让计算机系统从数据中“学习”并改进其性能&#xff0c;而无需进行明确的编程。Python因其易于学习、强大的库和广泛的应用场景&#xff0c;成为了机器学习的首选语言。本教程旨在帮助读者从零开始学习Python机…

APP开发突增20倍!安卓和鸿蒙你站哪边?

随着科技的快速发展&#xff0c;智能设备已经成为我们生活中不可或缺的一部分。 根据不少业内人士爆料&#xff0c;今年9月华为将发布mate70系列&#xff0c;而同时华为自己也官宣了"鸿蒙星河版"&#xff0c;也就是原生鸿蒙系统&#xff0c;将于今年4季度商用。这很…

31、链表-K个一组反转链表

思路&#xff1a; 首先知道如何反转链表&#xff0c;其次找出每组的开始节点和结束节点&#xff0c;然后对于不足与k个的链表保持原状。 代码如下&#xff1a; class Solution {public ListNode reverseKGroup(ListNode head, int k) {if (headnull||k1){return head;}ListN…

家居网购项目(Ajax验证用户名+上传图片)

文章目录 1.Ajax验证用户名1.程序框架图2.修改MemberServlet3.修改login.jsp4.结果展示 2.Ajax判断验证码是否输入正确1.修改MemberServlet2.修改login.jsp3.结果展示 3.Ajax添加购物车1.程序框架图2.修改CartServlet2.修改index.jsp3.解决问题—未登录直接添加购物车&#xff…

每日一题---OJ题: 有效的括号

片头 嗨! 小伙伴们,大家好! 我们又见面啦! 今天我们来一起尝试一下这道题目---有效的括号,准备好了吗? 我们开始咯! 说实话,我刚开始做这道题的时候也是一脸懵,怎么进行括号匹配呢? 别慌,我们一起画个图,分析分析括号匹配的过程~ 如下图所示,上方表示一个字符串数组,存放不…

【C++】力扣OJ题:找出只出现一次的数字

Hello everybody!这是我第一次写关于OJ题目的博客&#xff0c;因为正好学到完了C的STL库&#xff0c;就顺手刷了一些OJ题。 我今天要介绍的题目虽然是力扣上的简单题&#xff0c;但思想很巧妙&#xff0c;我觉得有必要和大家分享一下&#xff01; 1.题目 2.代码 class Solut…

【Go】原子并发操作

目录 一、基本概念 支持的数据类型 主要函数 使用场景 二、基础代码实例 开协程给原子变量做加法 统计多个变量 原子标志判断 三、并发日志记录器 四、并发计数器与性能监控 五、优雅的停止并发任务 worker函数 Main函数 应用价值 Go语言中&#xff0c;原子并发操…

飞机飞行数据三维可视化管控系统更智能、精准

近年来&#xff0c;随着无人化工厂和智能工厂在中国大量涌现&#xff0c;基于成熟的数字孪生理念&#xff0c;智能工厂三维可视化虚拟管控系统引领未来工业革命的先锋。数字孪生公司深圳华锐视点结合前沿的三维仿真、GIS和三维可视化技术技术&#xff0c;深度集成工厂生产、经营…

鸿蒙 Failed :entry:default@CompileResource...

Failed :entry:defaultCompileResource... media 文件夹下有文件夹或者图片名称包含中文字符 rawfile 文件夹下文件名称、图片名称不能包含中文字符