网站开发jsp需要什么jar包,网页链接调用服务需要开启还是关闭,wordpress google ad,网站开发设计费 怎么入账题目描述#xff1a;
有两种形状的瓷砖#xff1a;一种是 2 x 1 的多米诺形#xff0c;另一种是形如 L 的托米诺形。两种形状都可以旋转。 给定整数 n #xff0c;返回可以平铺 2 x n 的面板的方法的数量。返回对 109 7 取模 的值。
平铺指的是每个正方形都…题目描述
有两种形状的瓷砖一种是 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 mod1e97;
class Solution {
public:int numTilings(int n) {vectorvectorint dp(n1,vectorint(4));//定义dp二维数组//初始化dp[0][0]0;dp[0][1]0;dp[0][2]0;dp[0][3]1;for(int i1;in;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的方案数目}
};
