这是复制给 ref 的问题的一部分：
*您将获得 5xN 尺寸的地板。您有 2 种不同尺寸的图块：1x5 和 2x5。当然，您可以旋转瓷砖以获得另外 2 个瓷砖尺寸：5x1 和 5x2。您必须按以下方式使用这些瓷砖铺设地板：
您的任务是找出可以将瓷砖铺设在地板上的多种方式*
我能得到一些关于这种方法的帮助吗？提前致谢。
编辑：我现在明白什么时候我们必须计算用 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/
但是我不明白当有多个不同大小的瓷砖时如何制定 dp[n] 。您将获得一个大小为 5xN 的地板。您有 2 种不同尺寸的图块：1x5 和 2x5。
一些带有记忆功能的 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))
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句