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

简介: 力扣 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的方案数目
    }
};


相关文章
|
算法 测试技术 Android开发
LeetCode 周赛上分之旅 #45 精妙的 O(lgn) 扫描算法与树上 DP 问题
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
346 2
LeetCode 周赛上分之旅 #45 精妙的 O(lgn) 扫描算法与树上 DP 问题
|
Go
【LeetCode 热题100】DP 实战进阶:最长递增子序列、乘积最大子数组、分割等和子集(力扣300 / 152/ 416 )(Go语言版)
本文深入解析三道经典的动态规划问题:**最长递增子序列(LIS)**、**乘积最大子数组** 和 **分割等和子集**。 - **300. LIS** 通过 `dp[i]` 表示以第 `i` 个元素结尾的最长递增子序列长度,支持 O(n²) 动态规划与 O(n log n) 的二分优化。 - **152. 乘积最大子数组** 利用正负数特性,同时维护最大值与最小值的状态转移方程。 - **416. 分割等和子集** 转化为 0-1 背包问题,通过布尔型 DP 实现子集和判断。 总结对比了三题的状态定义与解法技巧,并延伸至相关变种问题,助你掌握动态规划的核心思想与灵活应用!
710 1
|
算法
dp算法 力扣309最佳买卖股票时机含冷冻期
dp算法 力扣309最佳买卖股票时机含冷冻期
|
存储 算法 Java
dp算法 力扣174地下城游戏
dp算法 力扣174地下城游戏
dp表,哈希表,力扣5.最长回文子串力扣1745.分割回文串IV力扣132.分割回文串II优先级队列(堆)是什么下面是手动实现小根堆力扣1046.最后一块石头的重量
dp表,哈希表,力扣5.最长回文子串力扣1745.分割回文串IV力扣132.分割回文串II优先级队列(堆)是什么下面是手动实现小根堆力扣1046.最后一块石头的重量
力扣123. 买卖股票的最佳时机 III(状态dp)
力扣123. 买卖股票的最佳时机 III(状态dp)
力扣370周赛 -- 第三题(树形DP)
力扣370周赛 -- 第三题(树形DP)
247 1
[leetcode ~dp ]279. 完全平方数
[leetcode ~dp ]279. 完全平方数
320 0