如何使用递归找到在走道中放置长度为 1 和 3 的块的方法数？

Question

我遇到了以下问题。给定一条长度为 n 的人行道，设计一个递归算法，计算出在人行道上放置尺寸为 1 和尺寸为 3 的方块的方法数。我了解将递归应用于此问题的策略 -

为人行道长度为 1、2 和 3 的情况输入基本情况。
假设您已经计算出在人行道上放置长度为 1 的方块的方法数
假设您已经计算出在人行道上放置长度为 3 的方块的方法数
添加 2) 和 3)

我的问题是我不知道如何编码 2) 和 3)。下面是我的代码 -

def countPatterns(n):
    if(n==1 or n==2):
        return 1
    elif(n==3):
        return 2
    elif(n<1):
        return 0
    else:
       # return 2) and 3)

Answer 1

此问题与 给定目标总和相同，您需要计算仅通过将数字 1 和 3 相加即可获得该目标总和的方法的数量。 示例：

sum = 4
ways:
  1: 1 + 1 + 1 + 1
  2: 1 + 3
  3: 3 + 1
So your function for sum = 4 should return 3.

我认为你的做法是错误的。这是我的解决方案：

def numWays(tSum):
    if tSum < 0:
        return 0
    if tSum <= 2:
        return 1
    return numWays(tSum - 1) + numWays(tSum - 3)

如何使用递归找到在走道中放置长度为 1 和 3 的块的方法数？

How do I find the number of ways to place blocks of length 1 and 3, in a walkway, using recursion?

algorithm

recursion