“计算尺寸为 5*N 的地板可以填充尺寸为 1*5 和 2*5 的瓷砖的方式数”的算法

Question

这是问题的一部分，复制以供参考：

*您的地板尺寸为 5xN。您有 2 种不同尺寸的图块：1x5 和 2x5。当然，您可以旋转图块以获得另外 2 个图块尺寸：5x1 和 5x2。您必须按照以下方式使用这些瓷砖铺地板：

1. 地面空间应完全被瓷砖覆盖。
2. 你不能打破瓷砖，即你必须完全使用瓷砖或根本不使用瓷砖。
3. 任何瓷砖都不应超出地面空间。
4. 瓷砖应平行于地板边界放置。

您的任务是找出在地板上铺设瓷砖的方法数量*

我可以在该方法上获得一些帮助吗？预先感谢。

编辑：我现在明白了，我们必须计算用 5*1 尺寸的瓷砖填充 5*N 尺寸的地板的方法。通过 dp 我们可以这样实现 dp[1]=1,dp[2]=1,dp[3]=1,dp[4]=1,dp[5]=2 dp[n]=dp[n-1]+dp[n-5] http://www.geeksforgeeks.org/count-number-ways-tile-floor-size-n-x-m-using-1-x-m-size-tiles/

但是我不明白当有多个不同尺寸的图块时如何制定 dp[n] 。 您的地板尺寸为 5xN。您有 2 种不同尺寸的图块：1x5 和 2x5。

Answer 1

Steve Kass 的

https://math.stackexchange.com/a/664236/468110的这个答案帮助我制定了递归式。发布我的解决方案，对于有人可能会觉得有用。 5*n 的第一列可以通过大小为 1*5 和 2*5 的多米诺骨牌平铺，总共有 10 种方式，如下图所示和命名： 我们将计算每种起始配置的数量，并将结果相加得到 f(n)。

任何 5*(n-1) 都可以扩展为 5*n 平铺，并且没有其他方法可以获得“类型 a”5*n 平铺。因此，有 f(n-1) 个“a 型”平铺。类似地，有 f(n-2)“b 型”5*n 平铺。类似地，类型 c 到 j 都具有 f(n-5) 平铺。 这使得：

f(n)=f(a)+f(b)+f(c)+f(d)+f(e)+f(f)+f(g)+f(h)+f(i)+f(j)
f(n)=f(a)+f(b)+8*f(c)
f(n)=f(n-1)+f(n-2)+ 8*f(n-5)

下面是使用和测试的c++代码：

int dp[1000000]={0};
int count(int n){
    if(n<0){
        return 0;
    }
    dp[0]=1;
    dp[1]=1;
    dp[2]=2;
    if(dp[n]>0){
        return dp[n];
    }

    dp[n] = count(n-1)+count(n-2)+8*count(n-5);

    return dp[n];    
}

Answer 2

一些具有记忆功能的 DP 应该可以解决这个问题：

def solve(x, memo={}):

    # Access already calculated values
    if x in memo:
        return memo[x]

    # Base cases
    if x < 0:
        raise Exception("Negative values are not allowed")
    if x < 2:
        return 1
    if x == 2:
        return 2

    # Place a 1x5 or a 2x5
    res = solve(x - 1) + solve(x - 2)

    # Fill a space of 5x5
    if 5 <= x:
        res += 8 * solve(x - 5)

    # Store result and return
    memo[x] = res
    return res

for x in range(100):
    print "{}: {}".format(x, solve(x))

Answer 3

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */   
int t,mod = 1e9+7;
cin>>t;
long long  dp[1000001];
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
dp[4] = 5;
dp[5] = 16;
for(int i=6;i<=1000000;i++){ 
    dp[i] = (dp[i-1] + dp[i-2] + (dp[i-5] * 8) % mod) % mod;
}
while(t--){
    int n;
    cin>>n;
    cout<<dp[n]<<endl;
}
return 0;
}