CODEWITHSUNDEEP
javadynamic-programming
Mina Samaan
Mina Samaan

Reputation: 11

Time complexity of path finding problem using dynamic programming

You are given x, y coordinates in the first quarter, and you try to reach the origin point (0,0) for example if you are at point (1,1) you can go to point 1,0 then 0,0. Return how many unique paths you can take. You can only move left or down.

This can be solved recursively and with memoization you can optimize the solution.

class Solution {
    public static int findUniquePaths(int x, int y){
        if(x == 0 || y == 0 ){
            return 1;
        }
        
        return findUniquePaths(x -1, y) + findUniquePaths(x, y -1);
    }
    
    //initialize mem to -1 before calling this function.
    public static int findUniquePathsDP(int x, int y,int[][] mem){
        if(x == 0 || y == 0 ){
            return 1;
        }
        if (mem[x][y] != -1){
            return mem[x][y];
        }
    
        mem[x][y] = findUniquePathsDP(x -1, y,mem) + findUniquePathsDP(x, y -1,mem);
        return mem[x][y];
    }
}

How can I find the time complexity of this problem with or without memoization?

Upvotes: 0

Views: 169

Answers (1)

Mina Samaan
Mina Samaan

Reputation: 11

I figured out that for recursive without mem , it will be O(2^(m+n)), but with mem, it will be O(m*n). However I am not 100 sure.

Upvotes: 1

Related Questions