Unique paths in a grid - a dynamic programming example

Author: Goran Trlin

This is a Python solution for the following algorithmic problem that can be found on LeetCode website (LeetCode problem 62, Unique paths).

Problem statement:

A robot is located at the top-left corner of a m x n grid. The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid. How many possible unique paths are there?

Example 1:

Input: m = 3, n = 7
Output: 28

The core ideas behind this solution:

  • This can be solved in a few different ways, including backtracking and dynamic programming.
  • Our code example is using dynamic programming
  • Solutions for up to m==2 , n==2 can be used as a basis
  • Every element after 2x2 grid is calculated as follows: if it is start of the row or start of the column, its value is 1. Otherwise, its value is a sum of the element above it and the one left to it.
  • Element values are stored in a table (tabulation technique) and the final solution is the table value at coordinates (m-1,n-1)

Video example for 4x4 grid:


Code:

'''
# Unique paths in a grid

A small example of using dynamic programming techniques for finding out the total number of unique paths between two points in a 2D grid.

Author:
Goran Trlin

Find more tutorials and code samples on:
https://playandlearntocode.com
'''


class Solution:
    # camelCase is used at the LeetCode website
    # def uniquePaths(self, m: int, n: int) -> int:
    def unique_paths(self, m: int, n: int) -> int:
        '''
        Dynamic programming solution
        On paper, it's just about summation of left and above at each new element
        An alternative would be backtracking.
        '''
        if m == 0 or n == 0:
            return 0

        if m == 1 and n == 1:
            return 1
        if m == 2 and n == 1:
            return 1
        if m == 1 and n == 2:
            return 1
        if m == 2 and n == 2:
            return 2

        cur_m = 1
        cur_n = 1

        if cur_m > m - 1:
            cur_m = m - 1

        if cur_n > n - 1:
            cur_n = n - 1

        table = [[0 for x in range(n)] for y in range(m)]  # create table
        done_m = False
        done_n = False

        while cur_m < m and cur_n < n:
            temp_m = 0
            temp_n = 0

            # go right:
            if done_m == False:
                while temp_n <= cur_n:
                    if temp_n == 0:
                        table[cur_m][temp_n] = 1
                    else:
                        table[cur_m][temp_n] = table[cur_m][temp_n - 1] + table[cur_m - 1][temp_n]
                    temp_n += 1

            # go down:
            if done_n == False:
                while temp_m <= cur_m:
                    if temp_m == 0:
                        table[temp_m][cur_n] = 1
                    else:
                        table[temp_m][cur_n] = table[temp_m][cur_n - 1] + table[temp_m - 1][cur_n]
                    temp_m += 1

            if cur_m == m - 1 and cur_n == n - 1:
                return table[cur_m][cur_n]  # done

            cur_m += 1
            cur_n += 1

            if cur_m > m - 1:
                done_m = True
                cur_m = m - 1

            if cur_n > n - 1:
                done_n = True
                cur_n = n - 1

        return 0

The code for this project can be found on GitHub.