“计算5 * N尺寸的地板可以用1 * 5和2 * 5尺寸的瓷砖填充的方式数量的算法” [英] Algorithm to 'count the number of ways a floor of size 5*N can be filled with tiles of sizes 1*5 and 2*5'

问题描述

以下是问题的一部分，其中的内容已复制以供参考：

Here is the part of the question with copied for ref:

*您的底池大小为5xN。您有2种不同大小的图块：1x5和2x5。当然，您可以旋转图块来获得2个以上的图块大小：5x1和5x2。您必须通过以下方式使用这些瓷砖进行地板铺设：

*You are given a floor of size 5xN. You have tiles of 2 different sizes: 1x5 and 2x5. Of course, you can rotate the tiles to get 2 more tile sizes: 5x1 and 5x2. You have to do the flooring using these tiles in the following way:

1. 地板空间应完全被瓷砖覆盖。


2. 您不能破坏瓷砖，即您必须完全使用瓷砖或根本不使用瓷砖。


3. 任何瓷砖都不应超出地面空间。


4. 标题应该平行于地板边界放置。

1. Floor space should be completely covered by tiles.
2. You cannot break tiles, ie, you have to use a tile entirely or not at all.
3. Any tile should not extend beyond the floor space.
4. Tiles should be placed parallel to the floor boundaries.

您的任务是查找进纸方式您可以将其铺在地板上*

Your task is to find the number of ways in which you can lay the tiles on the floor*

我可以从该方法获得一些帮助吗？

Can I get some help with the approach. Thanks in advance.

编辑：我现在明白了，当我们不得不计算用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-nxm-using-1-xm- size-tiles /

I understand now when we have to count the ways to fill floor of size 5*N with tiles of size 5*1. With dp we can achieve it like this dp[1]=1,dp[2]=1,dp[3]=1,dp[4]=1,dp[5]=2 and 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。

But I don't understand how to formulate dp[n] when there are more than one tile of different sizes. You are given a floor of size 5xN. You have tiles of 2 different sizes: 1x5 and 2x5.

推荐答案

一些带有备忘录的DP应该可以解决这个问题：

Some DP with memoization should do the trick:

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))

这篇关于“计算5 * N尺寸的地板可以用1 * 5和2 * 5尺寸的瓷砖填充的方式数量的算法”的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！