力扣 790. 多米诺和托米诺平铺(一维dp)

题目描述:

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

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

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

示例 1:

输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。

示例 2:

输入: n = 1
输出: 1

提示:

  • 1 <= n <= 1000

思路:

一眼动态规划

很容易想到,考虑第i列的平铺方式。

设计一个二维数组dp[i][j],表示以i列结尾的状态j的平铺方式的组合数目

第i列的情况有以下几种:

一个正方形都没有,记为状态 0,用dp[i][0]表示

只有上方的正方形,记为状态 1,用dp[i][1]表示

只有下方的正方形,记为状态 2,用dp[i][2]表示

上下两个正方形都有,记为状态 3,用dp[i][3]表示

那么第i列的这几种情况怎么由第i-1列的状态转移过来的呢?

dp[i][0]=dp[i-1][3]

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

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

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

这里只解释dp[i][1]

初始化,dp[0][0]=dp[0][1]=dp[0][2]=0,dp[0][3]=1

代码:

const int mod=1e9+7;
class Solution {
public:
    int numTilings(int n) {
        vector<vector<int>> dp(n+1,vector<int>(4));//定义dp二维数组
        //初始化
        dp[0][0]=0;
        dp[0][1]=0;
        dp[0][2]=0;
        dp[0][3]=1;
        for(int i=1;i<=n;i++){//题目要求取模,说明答案较大,考虑溢出问题
            dp[i][0]=dp[i-1][3]%mod;
            dp[i][1]=((long long)dp[i-1][2]+dp[i-1][0])%mod;
            dp[i][2]=((long long)dp[i-1][1]+dp[i-1][0])%mod;
            dp[i][3]=((long long)dp[i-1][3]+dp[i-1][0]+dp[i-1][2]+dp[i-1][1])%mod;

        }
        return dp[n][3];//dp[n][3]表示覆盖到了第n列,且状态为3的方案数目
    }
};

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

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

相关文章

df新增一列数据,并指定列名

方法1&#xff1a;直接指定df列名赋值为list即可 skill_info_df[age] age_list ps:list的长度要和df对齐 方法二 使用insert&#xff1a;

智能优化算法应用:基于象群算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于象群算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于象群算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.象群算法4.实验参数设定5.算法结果6.参考文献7.MATLAB…

AntDB数据库,通信行业20年变迁的见证者

2000年至今&#xff0c;通信行业发展已过了20多年。面对通信行业巨大的数据信息&#xff0c;数据库在行业发展中发挥了巨大的作用&#xff0c;AntDB数据库便是其中较为知名的一款数据库。在通信行业快速发展的阶段&#xff0c;打破国外产品与技术垄断是产业发展的重点与难点。面…

latex表格中内容过多如何换行【已解决】

最近在写论文的时候放了一个表格&#xff0c;但是表格看起来特别大&#xff0c;因为想让某些内容多的单元格完成换行操作 首先在main.tex引入makecell包 \usepackage{makecell} 然后回到表格找到你想换行的单元格&#xff0c;把\makecell{}加进去&#xff0c;然后在需要换行的…

深入浅出强化学习

目录 一、强化学习的概念 二、强化学习的特点 三、强化学习的训练过程 一、强化学习的概念 强化学习是一种机器学习方法&#xff0c;旨在教会算法如何通过与环境的交互来进行学习和决策。与传统的监督学习和无监督学习不同&#xff0c;强化学习侧重于学习与奖励和惩罚&#…

首批量子计算机即将部署!欧盟为波兰提供新算力优势

&#xff08;图片来源&#xff1a;网络&#xff09; 英国量子计算机开发商ORCA公司将为波兰的波兹南超级计算和网络中心&#xff08;PSNC&#xff09;提供两个PT-1光量子系统&#xff0c;以加速其在量子计算领域的研究和应用工作&#xff0c;如生物学、化学和机器学习领域。 …

机器人最优控制开源库 Model-based Optimization for Robotics

系列文章目录 文章目录 系列文章目录前言一、开源的库和工具箱1.1 ACADO1.2 CasADi1.3 Control Toolbox1.4 Crocoddyl1.5 Ipopt1.6 Manopt1.7 LexLS1.8 NLOpt1.9 qpOASES1.10 qpSWIFT1.11 Roboptim 二、其他库和工具箱2.1 MUSCOD2.2 OCPID-DAE12.3 SNOPT 前言 机器人&#xff…

Conductor之动态分叉

Conductor之动态分叉 动态分叉 关于动态分叉&#xff0c;参考1 动态分叉 有时候我们希望在运行时能动态添加分叉任务&#xff08;注意是分叉任务&#xff0c;不是动态任务&#xff09;&#xff0c;Conductor当前版本也是支持的&#xff0c;但是经过试验的版本只支持串行分叉&…

进程间通信方式——管道

进程间通信方式——管道 1、管道2、匿名管道2.1 创建匿名管道2.2 进程间通信 3、有名管道3.1 创建有名管道3.2 进程间通信 4、管道的读写行为 原文链接 1、管道 管道的是进程间通信&#xff08;IPC - InterProcess Communication&#xff09;的一种方式&#xff0c;管道的本质…

进程(process) vs 线程(Thread)

文章目录 前言一、进程&#xff08;process) vs 线程&#xff08;Thread&#xff09;引用自维基百科引用自CSDN INCOE AI引用自 geeksforgeeksOS( Operating System )如何调度线程的线程锁的核心原理是什么? 总结 前言 &#x1f680; 多方面理解进程(process) &#xff0c;线…

Python程序的计时

# -*- coding: UTF-8 -*- import timedef fun():time.sleep(5)sinceTime time.time() print("开始计时时刻&#xff1a;", sinceTime) fun() endTime time.time() print("结束时刻&#xff1a;", endTime) program_time endTime - sinceTime print(&quo…

振南技术干货集:各大平台串口调试软件大赏(5)

注解目录 &#xff08;串口的重要性不言而喻。为什么很多平台把串口称为 tty&#xff0c;比如 Linux、MacOS 等等&#xff0c;振南告诉你。&#xff09; 1、各平台上的串口调试软件 1.1Windows 1.1.1 STCISP &#xff08;感谢 STC 姚老板设计出 STCISP 这个软件。&#xf…

特殊二叉树——堆

&#x1f308;一、堆的基本概念 1.堆&#xff1a;非线性结构&#xff0c;是完全二叉树 2.堆分为大堆和小堆。 大堆&#xff1a;树中任意一个父亲都大于等于孩子&#xff0c;根节点值大于等于其所有子孙节点的值。 小堆&#xff1a;树中任意一个父亲都小于等于孩子&#xff0c;…

【pytorch】深度学习入门一:pytorch的安装与配置(Windows版)

请支持原创&#xff0c;认准DannisTang&#xff08;tangweixuan1995foxmail.com&#xff09; 文章目录 第〇章 阅读前提示第一章 准备工作第一节 Python下载第二节 Python安装第三节 Python配置第四节 Pycharm下载第五节 Pycharm安装第六节 CUDA的安装 第二章 Anaconda安装与配…

Kaggle-水果图像分类银奖项目 pytorch Densenet GoogleNet ResNet101 VGG19

一些原理文章 卷积神经网络基础&#xff08;卷积&#xff0c;池化&#xff0c;激活&#xff0c;全连接&#xff09; - 知乎 PyTorch 入门与实践&#xff08;六&#xff09;卷积神经网络进阶&#xff08;DenseNet&#xff09;_pytorch conv1x1_Skr.B的博客-CSDN博客GoogLeNet网…

Django-Redis

NoSQL&#xff1a;(不支持sql语句) Redis MongoDB Hbase hadoop Cassandra hadoop key-value数据库&#xff08;非关系性数据库&#xff09; redis优势 性能高&#xff0c;读取速度快&#xff0c;存在内存中 Redis应用场景 用来做缓存 在某些特定场景下替代传统数据库---社交…

数据爬取+可视化实战_告白气球_词云展示----酷狗音乐

一、前言 歌词上做文本分析&#xff0c;数据存储在网页上&#xff0c;需要爬取数据下来&#xff0c;词云展示在工作中也变得日益重要&#xff0c;接下来将数据爬虫与可视化结合起来&#xff0c;做个词云展示案例。 二、代码 # -*- coding:utf-8 -*- # 酷狗音乐 通过获取每首歌…

Python (十八) lambda

程序员的公众号&#xff1a;源1024&#xff0c;获取更多资料&#xff0c;无加密无套路&#xff01; 最近整理了一份大厂面试资料《史上最全大厂面试题》&#xff0c;Springboot、微服务、算法、数据结构、Zookeeper、Mybatis、Dubbo、linux、Kafka、Elasticsearch、数据库等等 …

svn合并冲突时每个选项的含义

合并冲突时每个选项的含义 - 这个图片是 TortoiseSVN&#xff08;一个Subversion&#xff08;SVN&#xff09;客户端&#xff09;的合并冲突解决对话框。当你尝试合并两个版本的文件并且出现差异时&#xff0c;你需要解决这些差异。这个对话框提供了几个选项来处理合并冲突&…

Python中用于机器学习的Lazy Predict库

Python是一种多功能语言&#xff0c;你可以用它来做任何事情。Python的一个伟大之处在于&#xff0c;有这么多的库使它变得更加强大。Lazy Predict就是其中一个库。它是机器学习和数据科学的一个很好的工具。在本文中&#xff0c;我们将了解它是什么&#xff0c;它做什么&#…