Introduction to Dynamic Programming on Grids:

Analysis of following Algorithms:

· When a Cost Matrix is given, find the least expensive path in a grid.

· Counting the number of ways to get from one point to another in the provided directions.

Finding Least Expensive Path

Assumption: All costs are positive

Problem Statement: Find a minimum-cost path from cell (0,0) to cell (x,y) given a cost matrix Cost[][], where Cost[i][j] specifies the cost of visiting cell with coordinates (i,j). (All costs are positive integers, we suppose.)

To solve this, it is simple to see that to reach a grid location (i,j), you must have come from one cell above, i.e. (i-1,j), or one cell to your left, i.e. (i,j-1). This indicates that the following recurrence relation will determine the cost of visiting cell (i,j):

Reccurence Relation :

MinCost(i,j) = min(MinCost(i-1,j),MinCost(i,j-1)) + Cost[i][j]

Now Solving for base Cases :

The difficulty of determining the lowest-cost path is nearly solved now. The basic cases’ values, the topmost row and the leftmost column, are now computed. A cell in the topmost row can only be accessed from the cell to its left. In the case of a zero-based index

MinCost(0,j) = MinCost(0,j-1) + Cost[0][j]

MinCost(i,0) = MinCost(i-1,0) + Cost[i][0]

Cost of getting to cell (0,j) = Cost of getting to cell (0,j-1) + Cost of going to cell (0,j) (0,j) Similarly,

Time Complexity:

For this code two loops are running therefore O(rows*columns)

Alternatives to this code:

Brute forcing and storing the values in an array then finding minimum of them that will be the minimum cost path.

Time complexity for brute force approach will be O(nm+n), m*n for traversing through the whole matrix and

N for finding best solution after traversing the whole array.

Space Complexity:

O(nm) for storing the distance of every cell to every cell

Another Approach is to use greedy approach and select the cell with minimum value and keep traversing towards the goal cell (x,y) if the minimum value is towards the left then choose left and then repeat the selection process again.

Worst-Case time-complexity of this algorithm is O(m+n),but it might not reach the required (x,y) cell since minimum value might not help reach

The required cell (x,y) always.

Why Dynamic Programming is better ?

With Space Complexity of O(mn), it is an intelligent brute-force where we

Compute the steps left to cell and above it since these are the only ways we can reach a particular cell (x,y) and worst time complexity O(mn)

And best being O(m+n) that is diagonal of the matrix comparing it to greedy

it might not be necessary that with greedy approach, we will reach the destination by always going towards minimum. In brute-force approach distance from all nodes to nodes will be stored there making unnecessarily

increasing space complexity and time complexity also for finding the most optimum solution we will have to traverse through the storage that might require maximum O(mn) for traversing through the whole matrix.

Therefore Dynamic Programming is a definitive better approach.

A more performative approach

In dynamic programming approach we store the results for an already calculated sub-tree re-computation.

We can optimize space-complexity by using only by two rows, since only two cells are used at once for updating the values therefore

Space Complexity — O(2*number_of_columns)

Counting the number of ways to get from a starting point to a destination-

Problem: Given a matrix with M rows and N columns, to find the number of ways to reach cell i,j from starting (0,0) given restrictions that one can travel only one cell down or right.

We can relate this problem with the previous one to find the recurrence relation for this problem,

we can find the number of ways to solve this problem for a given (I,j) cell by summing the number of ways of one left and one cell above that is numofways[i-1][j] and numofways[i][j-1].

Therefore Reccurence Relation

numWays(i,j) = numWays(i-1,j) + numWays(i,j-1)

Now, for base case for first row number of ways of reaching a cell is 1, since you can come from one side only and similarly for first column one can come down only in one way.

The answer will be at the last cell of matrix that is numWays[n-1][m-1]

Alternatives :

Alternatives for above algorithms applies here as will.

The above two were dynamic programming problems since both of these satisfied the following two properties –

Optimal Sub-Structure — Optimal solutions to a problem involves solutions optimal solutions to sub-problem

Overlapping Sub-Problems- Subproblems once computed should be stored in the table for re-use.

Lets talk about on a variation of the first these problems if moving diagonally was allowed then the

Reccurence relation for the above problems would be –

1) MinCost(I,j) = min(MinCost(i-1,j),MinCost[i][j-1],MinCost[i-1][j-1]) + Cost[I,j]

2) numWays(I,j) = numWays(i-1,j) + numWays(i-1,j-1) + numWays(i,j-1)

Usage:

• Used to find minimum cost path in real-time
• Real-time calculation of shortest paths to find most effecient path

Advantages over Brute-force:

• Intelligently skips over many cells no need to go over all cells.
• No re-computation needed for sub-trees.

Dis-Advantages over Greedy-Algorithms:

- Sometimes greedy will reach faster by taking minimum cost path always

Conclusion:

- Dynamic program approach works best when space complexity is O(Number_of _columns)

- Sometimes greedy will reach faster but not guaranteed to reach the solution.

- Number of ways to reach a destination to know in advance in case one path cannot be traversed.

The intention was to give intuition to problems involving dynamic programming on grids, hope it was helpful !