I have been given the following problem. Given a walkway of length n, design a recursive algorithm that tells the number of ways to place blocks of size 1 and size 3 on the walkway. I understand the strategy to apply recursion to this problem -

1. Put in base cases for cases where the walkway is of lengths 1, 2, and 3.
2. Assume that you already have figured out the number of ways to place blocks of length 1 on the walkway
3. Assume that you already have figured out the number of ways to place blocks of length 3 on the walkway
4. Add 2) and 3)

My problem is that I don't know how to code 2) and 3). Here's my code below -

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)  

CodePudding user response：

This problem is the same as given the target sum and you need to count number of ways that you can get that target sum just by adding numbers 1 and 3. Example:

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

I think your approach is wrong. Here is my solution:

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