plse fast i have 30 min

6. We want to count the number of ways to climb a staircase of n steps, where you can take ehther 1,2 , or 3 steps at a time. The input to the problem is a positive integer n representing the number of steps in the staircase. The output is the mumber of ways to climb the staircase. For example, for n=3, there are 4 ways to climb the staircase (1+1+1,1+2,2+1,3). For n=4, there are 7 ways to climb the staircase (1+1+1+1,1+1+2,1+2+1,2+1+1,2+2,1+3,3+1) You can solve using a recursive fumction or dynamic programming. The recursive function solves the problem by breaking it down into smaller subproblems, l.e., counting the number of ways to climb a staircase of n1 steps, n2 steps, and n3 steps, and adding their results. The dymamic programming solution solves the problem by storing the results of the subproblems and reusing them, which avoids recomputing the same subproblems and significantly improves the time complexity. a. Write the pseucio code of the dynamic programming solution to this problem ( 20 points) Solve the problem for n=9 using your algorithm. ( 10 points)