帮我写一个java代码,要求如下: 小团子最近买了一个房子,准备铺地板,不过这么房子就很奇怪,整体大小是3*n。现在我们需要用1*3的瓷砖去铺满3*n的房间,小团子需要知道有多少种方案呢? (谁画的图,这么丑) 输入格式 输入一个n(n<=100) 输出格式 输出结果并对1e9+7取余。 样例输入 10 样例输出 28
时间: 2024-02-12 17:04:36 浏览: 30
以下是 Java 代码实现:
```
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 0;
dp[2] = 3;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i-1]*2 + dp[i-2]*3;
dp[i] %= 1000000007;
}
System.out.println(dp[n]);
}
}
```
解题思路:
这是一道动态规划题目,我们可以用 dp[i] 表示铺满 3*i 的房间有多少种不同的方案。
- 当 i=0 时,dp[0] = 1,表示空房间可以看作是一种铺满的方案;
- 当 i=1 时,dp[1] = 0,由于瓷砖的长度为 3,所以无法铺满 1*3 的空间;
- 当 i=2 时,dp[2] = 3,可以分别用三种不同的方式铺满 3*2 的空间,即两个连续的 1*3 瓷砖、两个相邻的 1*3 瓷砖、一个“L”型的 1*3 瓷砖;
- 当 i>2 时,我们可以把 3*i 的空间分为两个部分:一个是 3*(i-1) 的空间,另一个是 3*2 的空间。因为从 3*(i-1) 的空间铺满 3*i 的空间只需要加上一个 1*3 的瓷砖,所以有 dp[i-1] 种方案,同理,从 3*(i-2) 的空间铺满 3*i 的空间需要加上两个 1*3 的瓷砖,有 dp[i-2] 种方案。加起来即为 dp[i] 的方案数。
最后记得对 1e9+7 取余。