LeetCode每日一题——790. 多米诺和托米诺平铺

简介: 有两种形状的瓷砖:一种是 2 x 1 的多米诺形,另一种是形如 “L” 的托米诺形。两种形状都可以旋转。

题目

有两种形状的瓷砖:一种是 2 x 1 的多米诺形,另一种是形如 “L” 的托米诺形。两种形状都可以旋转。

2345_image_file_copy_7.jpg

给定整数 n ,返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同,当且仅当面板上有四个方向上的相邻单元中的两个,使得恰好有一个平铺有一个瓷砖占据两个正方形。

示例

示例 1:

2345_image_file_copy_8.jpg

输入: n = 3

输出: 5

解释: 五种不同的方法如上所示。

示例 2:

输入: n = 1

输出: 1

提示:

1 <= n <= 1000

思路

动态规划:

dp数组定义为dp[i][0]表示到达i-1块全部填满的可能情况,dp[i][0]表示到达i-1块缺一块的可能情况(这里缺的一块不分上下)。

状态转移方程为:

1.dp[i][0]=dp[i-1][0]+dp[i-2][0]+dp[i-1][1]

2.dp[i][1]=dp[i-2][0]*2+dp[i-1][1]

题解

class Solution:
    def numTilings(self, n: int) -> int:
    # n=1,2的情况直接返回
        if n==1:return 1
        if n==2:return 2
        dp=[[0]*2 for _ in range(n)]
        # 赋边界值
        dp[0]=[1,0]
        dp[1]=[2,2]
        for i in range(2,n):
            dp[i][0]=dp[i-1][0]+dp[i-2][0]+dp[i-1][1]
            dp[i][1]=dp[i-2][0]*2+dp[i-1][1]
        return dp[-1][0]%(10**9+7)
目录
相关文章
|
存储 传感器 定位技术
【NI Multisim 14.0原理图设计基础——元器件分类】
一、元器件分类 NI Multisim 14.0不仅提供了数量众多的元器件符号图形,而且还设计了元器件的模型,并分门类地存储在各个元器件库中。下面按照元器件库的命名不同详细介绍常用的元器件。 1.电源库 单击“元器件”工具栏中的“放置源” 按钮,Sources 库的“系列”栏包括以下几种,如图所示: 电源(POWER-SOURCES):包括常用的交直流电源、数字地、地线、星形或三角形连接的三相电源、VCC、VDD、VEE、VSS 电压源,其元器件”栏下内容如图所示: 电压信号源(SIGNAL-VOLTAG…):包括交流电压、时钟电压、脉冲电压、指数电压、FM、AM等多种形式的电压信号,其“元器
16932 3
【NI Multisim 14.0原理图设计基础——元器件分类】
|
7月前
|
人工智能 自然语言处理 安全
【2025】世界顶级AI模型本地部署私有化完整版教程 DeepSeek-R1+Ollama+ChatboxAI合体,瞬间升级你的个人电脑秒变智能神器!
震撼发布!让你的电脑智商飙升,DeepSeek-R1+Ollama+ChatboxAI合体教程,打造私人智能神器!
984 42
【2025】世界顶级AI模型本地部署私有化完整版教程 DeepSeek-R1+Ollama+ChatboxAI合体,瞬间升级你的个人电脑秒变智能神器!
|
9月前
|
机器学习/深度学习 数据采集 人工智能
基于Qwen 2.5的世界科学智能大赛冠军方案
本方案基于通义千问模型,采用多阶段的Easy-to-Hard数据合成方法,模拟人类学习的由简单到困难的思路,逐阶段构造多样化的训练数据。数据生成阶段,训练数据的标签,引入了“Chain-of-Thought”思维链模式,生成多样化的推理路径,逐步对齐推理Scaling Law。训练阶段,采用了LoRA对通义千问32B模型在合成数据集上进行参数高效微调。推理阶段,使用了4bit低精度量化,并结合vLLM框架进行推理加速,最终达到准确性、效率和显存利用率的统一。
578 2
基于Qwen 2.5的世界科学智能大赛冠军方案
|
9月前
|
存储 编解码 Dart
腾讯开源混元视频生成模型,这效果!太稳了吧!
腾讯开源了HunyuanVideo,这是一个超过130亿参数的视频生成模型,具备高性能的图像-视频联合生成能力。通过创新的模型架构和高效的训练基础设施,HunyuanVideo在视觉质量、运动多样性和文本-视频对齐等方面表现出色,超越了多个现有模型。该项目旨在推动视频生成技术的发展,促进社区交流与创新。
580 11
腾讯开源混元视频生成模型,这效果!太稳了吧!
|
11月前
|
网络协议 安全 Linux
Kali渗透测试:拒绝服务攻击(一)
Kali渗透测试:拒绝服务攻击(一)
541 2
|
Java 应用服务中间件 Nacos
Spring Cloud 常用各个组件详解及实现原理(附加源码+实现逻辑图)
Spring Cloud 常用各个组件详解及实现原理(附加源码+实现逻辑图)
310 3
Spring Cloud 常用各个组件详解及实现原理(附加源码+实现逻辑图)
|
运维 监控 持续交付
自动化运维在云计算时代的演进与实践
【7月更文挑战第27天】 随着云计算技术的飞速发展,自动化运维已成为企业提升效率、保障服务质量的关键。本文将深入探讨自动化运维在云计算背景下的发展趋势,以及如何通过实践案例来构建和优化自动化运维体系。我们将从自动化运维的定义出发,分析其在云环境中的重要性,并结合实际案例,展示自动化运维的实施策略和成效评估。文章旨在为运维专业人员提供一套系统的方法论,帮助他们在云计算时代中把握自动化运维的脉搏,实现运维工作的高效和可靠。
148 2
|
10月前
|
弹性计算 并行计算 双11
阿里云服务器多少钱一年?2024年11月最新价格表,爆款配置清单
2024年双十一期间,阿里云推出多款优惠云服务器配置。最便宜的轻量应用服务器2核2G、3M带宽、50GB ESSD云盘,仅需36元一年;ECS云服务器2核2G、3M带宽、40GB ESSD Entry云盘,99元一年;ECS u1实例2核4G、5M带宽、80GB ESSD Entry盘,199元一年。更多配置详见官网。
972 0
|
监控 关系型数据库 MySQL
Flink CDC产品常见问题之使用3.0测试mysql到starrocks启动报错如何解决
Flink CDC(Change Data Capture)是一个基于Apache Flink的实时数据变更捕获库,用于实现数据库的实时同步和变更流的处理;在本汇总中,我们组织了关于Flink CDC产品在实践中用户经常提出的问题及其解答,目的是辅助用户更好地理解和应用这一技术,优化实时数据处理流程。
|
Java 网络安全
SSL peer shut down incorrectly
SSL peer shut down incorrectly
1057 0