“计算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:
- 地板空间应完全被瓷砖覆盖。
- 您不能破坏瓷砖,即您必须完全使用瓷砖或根本不使用瓷砖。
- 任何瓷砖都不应超出地面空间。
- 标题应该平行于地板边界放置。
- Floor space should be completely covered by tiles.
- You cannot break tiles, ie, you have to use a tile entirely or not at all.
- Any tile should not extend beyond the floor space.
- 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屋!