Java实现 LeetCode 790 多米诺和托米诺平铺(递推)
2023-09-14 08:58:01 时间
790. 多米诺和托米诺平铺
有两种形状的瓷砖:一种是 2x1 的多米诺形,另一种是形如 “L” 的托米诺形。两种形状都可以旋转。
XX <- 多米诺
XX <- “L” 托米诺
X
给定 N 的值,有多少种方法可以平铺 2 x N 的面板?返回值 mod 10^9 + 7。
(平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同,当且仅当面板上有四个方向上的相邻单元中的两个,使得恰好有一个平铺有一个瓷砖占据两个正方形。)
示例:
输入: 3
输出: 5
解释:
下面列出了五种不同的方法,不同字母代表不同瓷砖:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY
提示:
N 的范围是 [1, 1000]
class Solution {
//dp[i][0]是第n行,并且是平铺
//dp[i][1]是第n行,不平铺的
// public int numTilings(int N) {
// long[][] dp = new long[N+1][3];
// dp[0][0] = 1;
// dp[0][1] = 0;
// int MOD = 1000000007;
// for(int i = 1 ; i <= N ; ++i){
// long temp = i < 2 ? 0 : dp[i -2][0];
// dp[i][0] = (temp + dp[i-1][0] + 2 * dp[i-1][1]) % MOD;
// dp[i][1] = (temp +dp[i-1][1]) % MOD;
// }
// return (int)dp[N][0];
// }
public int numTilings(int N) {
int mod = 1000000007;
int[] dp = new int[N+3];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
dp[3] = 5;
for(int i = 4; i <= N; i++){
//这里全是平铺的,
//我当前这一位,可以是我上一位平铺的+一个2*1的,
//我可以把1*2的放到最上面,也可以放在最下面,是两种可能,所以*2
//还可以是我三位前的那个,因为可以是两个L
//但这里,我开头或者结尾可能是L的,如果我们在那个基础上加上L
//可能会导致重复,以至于要/2,也就变成了三位前的那个*2/2==1
dp[i] = (2*(dp[i-1] % mod) % mod + dp[i-3] % mod) % mod;
}
return dp[N] % mod;
}
}
相关文章
- java转换字符串为时间_JAVA字符串转日期或日期转字符串
- java double转decimal_Java中Double与BigDecimal的相互转换
- java xml解析框架_JAVA解析xml的五种方式对比
- c++和java哪个好学_c++语言和Java语言,初学者该如何选择?「建议收藏」
- MySQL字段类型如何转为java_Java JDBC中,MySQL字段类型到JAVA类型的转换
- db4o java,db4o Java版性能测试评估
- JAVA数据库连接池_java与数据库的连接怎么实现
- Java递归详解_java难不难学
- 【JAVA面试必会】JMM高并发详解(java内存模型、JMM三大特征、volatile关键字 )「建议收藏」
- java socket详解_Java Socket 编程原理及教程「建议收藏」
- Java 连接 MySQL 数据库简易实现(java连mysql)
- Java实现MSSQL数据库连接(java连接mssql)
- 数据库轻松搞定:用Java访问Oracle数据库(java访问oracle)
- Java与Linux搭配,开发无限可能(java与linux)
- 使用Java实现Redis数据存储(redis集成java)
- Java编程在Linux上的应用(java编程 linux)
- Java搭配MySQL,实现创新跳跃的可能(java 与mysql)
- 使用Linux安装Java轻松搞定!(linux java安装)
- Oracle数据库中调用Java实现可扩展应用程序(oracle内嵌java)
- 秘籍学习实现纯Java版Redis(纯java版redis)
- 实现Java认证让你离Oracle更近一步(java认证oracle)
- Java与Oracle同步一种新的数据库模式(java同步oracle)
- 使用Java实现Redis锁定的实现(redis锁定 java)
- Redis中使用Java快速实现自增(redis自增 java)