POJ2663

Written by    20:37 March 27, 2015 

POJ2663

Tri Tiling
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 8737 Accepted: 4554

Description

In how many ways can you tile a 3xn rectangle with 2×1 dominoes?
Here is a sample tiling of a 3×12 rectangle.

Input

Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 <= n <= 30.

Output

For each test case, output one integer number giving the number of possible tilings.

Sample Input

Sample Output

Source

简单DP题目。

题意是给定一个3×n的矩形,然后用2×1的矩形来填满,问有多少种不同的填充方案。

令3×2为一个单位,首先要明白的是如果n为奇数的话无论如何也填不满。

对于每一个单位矩形,有下列三种方式可以填满:

0291

然后也有下列两种方式可以作为衔接:

0292

进而可以推出 DP[i] = 3×DP[i-1] + 2×(DP[i-2]+DP[i-3]+Dp[i-4]+ … + DP[0])

想要理解清楚这个DP思想,可以先看看下图对于DP[i]的定义:

0293

如图所示DP[i]和DP[i-1]是前者包含后者的关系,刚开始的时候总是喜欢理解成互相独立的关系所以很容易昏了头。

DP算法其实就是数学归纳法,关键在于找出那个状态转移方程。

再来看这道题目,因为数据范围只有30,所以直接打表即可。

 

Category : acmstudy

Tags :