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
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.