首页 > 试题广场 >

牛牛爱花

[编程题]牛牛爱花
  • 热度指数：1223 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
 牛牛有一个3*n的土地。这个土地有3行，n列。牛牛想在土地上种至少一朵花。

为了花儿能够茁壮成长，每一朵花的上下左右四个方向不能有其他的花。问有多少种种花的方案。

为防止答案过大，答案对1e9+7取模。

示例1

输入

1

输出

4

说明

只有1列，用1代表花，0代表空地。这一列的种法可能是[1,0,0],[0,1,0],[0,0,1],[1,0,1]四种

备注:
算法知识视频讲解
开通博客
头像 积极的防守者
发表于 2020-02-11 22:23:48
最优解法 用二进制[0~7]代表每一列的种花情况。用代表有列且最后一列的种花情况为，通过枚举有列的最后一列花的情况来转移。可以用滚动数组优化空间复杂度。因为每一列种花情况只有5个状态是有效的，所以总的时间复杂度为，滚动数组优化后只用了一个2*8的辅助数组，空间复杂度可以视为。 int solve(i 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 认认真真coding
发表于 2021-08-08 14:28:47
题目描述 牛牛有一个3*n的土地。这个土地有3行，n列。牛牛想在土地上种至少一朵花。 为了花儿能够茁壮成长，每一朵花的上下左右四个方向不能有其他的花。问有多少种种花的方案。 为防止答案过大，答案对1e9+7取模。 方法一：动态规划思想求解 求解思路对于本题目的求解，我们采用动态规划的思想进行问题的求 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 不会做题的小菜鸡
发表于 2021-09-13 17:04:35
思路 题目分析 我们有一块大小为3*n的土地，n即为我们的输入 这块土地可以种花，要求花和花之间上下左右不可相邻，且至少要种一朵，只要花种的位置不同就视作不同的种植方案 输出可以种花的方案数 我们发现，种植的行数是固定的 = 3 因此每一列的种植情况是死的，我们暂时不考虑至少要种一朵这个条 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-08-04 22:23:50
思路： 题目的主要信息： 一个的土地，至少种一株花 当某个位置种了花，其上下左右不能再有花，问种花的方案数 数比较大，需要返回 方法一：动态规划具体做法：首先解决上下花不能邻近的问题，如下图：图中每列表示三行中的任意一列，对于任意一列，我们以0表示不种花，1表示种花，我们可以发现二进制数为3、6 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 呆喵挠琴
发表于 2021-09-05 18:07:33
思路： 题目的主要信息：种花土地大小为3*n，1≤n≤1e5，根据题目要求，种花时需要满足以下两种条件： 土地上至少要有一朵花 每朵花的上下左右不能有花 方法一：动态规划 根据题目信息，总共有n列3x1的土地，如果用1代表在这格上种花，0代表这格不种花，在3x1的土地上种花有以下几种情况：我们用 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划 数组
难度：
9条回答 3606浏览

热门推荐

通过挑战的用户

查看代码

相关试题

牛牛爱花

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号