Count steps using Dynamic prog

 #include <iostream>

#include <cstring>

using namespace std;

// A child is running up a staircase with n steps and can hop either 1 step, 2 steps, or 3

// steps at a time. Implement a method to count how many possible ways the child can run up the

// stairs.

int countSteps(int n, int mem[])

{

    if(n<0)

        return 0;

        

    

    if(n==0 || n==1)

        return 1;

    

    if(mem[n]) return mem[n];

    

    mem[n] = countSteps(n-1, mem) + countSteps(n-2, mem) + countSteps(n-3, mem);

    return mem[n];

}

int main() {

// your code goes here

int mem[50];

memset(mem, 0, 50*sizeof(int));

cout << countSteps(10, mem) << endl;

return 0;

}