Grid travel (find path by dynamic prog)

 #include <iostream>

#include <cstring>

using namespace std;

// Imagine a robot sitting on the upper left corner of grid with r rows and c columns.

// The robot can only move in two directions, right and down, but certain cells are "off limits" such that

// the robot cannot step on them. Design an algorithm to find a path for the robot from the top left to

// the bottom right.

bool findPath(int r, int c, int currow, int curcol, int path[], int top)

{

    

    if(r<0 || c<0)

        return false;

        

    if(r ==1 && c == 1)

    {

        return true;

    }

    

    if(r == currow+1 && c == curcol+1)

        return true;

    

    if(currow+1 > r)

        return false;

        

    if(curcol+1 > c)

        return false;

        

    if(curcol ==0 && currow == 2)   // 1=off-limit cell, 0=ok

        return false;

    

    if(curcol ==1 && currow == 4)   // 1=off-limit cell, 0=ok

        return false;

        

    path[top] = 0; //down   

    bool b1 = findPath(r, c, currow+1, curcol, path, top+1);

    

    if(b1) return b1;

    

    path[top] = 1; //right

    bool b2 = findPath(r, c, currow, curcol+1, path, top+1);

    

    if(b2) return b2;

    

    return false;

}

void printPath(int a[])

{

    for(int i=0; i<50 && a[i]!=-1; i++)

        cout << ((a[i] == 0) ? 'd':'r')  << "-->";

}

int main() {

// your code goes here

int path[50];

memset(path, -1, 50*sizeof(int));

findPath(5, 5, 0, 0, path, 0);

printPath(path);

return 0;

}

output:

d-->r-->d-->d-->r-->d-->r-->r-->

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;

}