This post is completed by 2 users Login To Mark Completed

1

Add to List Add To List..(Max 5) Close Save

Medium

Count All Paths from Top left to bottom right in Two Dimensional Array including Diagonal Paths

Objective: Count all the paths from left top corner to the right bottom corner in two-dimensional array.

Input: Two Dimensional array

Output: No of paths.

Approach :

1. Recursive

The recursive solution to this problem is similar to Print All Paths from Top left to bottom right in Two Dimensional Array

But the Time complexity will be exponential because there will be many sub-problems that will be solved again and again to get the final solution. read this: "Dynamic programming vs Recursion

2. Dynamic Programming (Better Solution)

Create two-dimensional resultCount array to store the number of paths from top left corner.

Base Case: To reach any cell in either the first row or column from the first cell(top left at 0,0) will be 1.

You can reach any cell in 3 different ways, from the left, from the top, and from the diagonal. So the total no of paths to reach that cell will be the sum of all the paths to reach to left, top, and diagonal cells. see picture

Example:

Run This Code

Code:

Output:

No of Paths By Recursion: 13
No of paths By Dynamic Programming: 13

---

---

Also Read:

- Maximum Surpasser in the given array Hard
- Counting Sort Medium
- Implement Queue Using Stacks Medium
- Linear Search Algorithm Beginner
- Override the compare function for Collections.sort method Beginner
- Rearrange the Array of Given Range N, such that A[i]=i Medium
- Populate Next Siblings Pointers in a Given Binary Tree OR Populate Next Right Pointers in Each Node Hard
- Dynamic Programming - Subset Sum Problem Hard

---