Dynamic programming

Dynamic programming is a popular way to solve some algorithmic problems. The main approach of this type of task is that to find the best solution at the \(N-th\) step, you have to check the solution at the \(N-1\) step.

Robot task 1

Problem statement

This is a classic example of a dynamic programming problem. Suppose we have a square board of size NxN. And there is robot that stay on the top left cell of the board. We need to count ways that robot can use to get to the bottom right corner of the field. Assuming the robot can only walk to the right and down.

So if we are talking about a 3x3 cell, there are 6 possibilities. All of them are described in the following cell:

[→] [→] [↓] | [→] [↓] [ ] | [→] [↓] [ ]
[ ] [ ] [↓] | [ ] [→] [↓] | [ ] [↓] [ ]
[ ] [ ] [ ] | [ ] [ ] [ ] | [ ] [→] [ ]
----------------------------------------
[↓] [ ] [ ] | [↓] [ ] [ ] | [↓] [ ] [ ]
[↓] [ ] [ ] | [→] [↓] [ ] | [→] [→] [↓]
[→] [→] [ ] | [ ] [→] [ ] | [ ] [ ] [ ]

Idea

For a cell with coordinates \((i,j)\), we can count the number of passes by simply summing the number of passes for the cell \((i-1, j-1)\). So we can simply use a recursion that sums the number of passes for the top cell and the left cell.

To apply the function once to each cell, you can simply save the counts for the cells and use them again in the next steps - this method is called memorisation. So in each iteration you have to check if the number of paths to the cell in question is already known, and if so, just return the result of the previous steps.

Trick

There is only one way to reach the top row and left column, so you can fill them before the recursion. There’s great convenience in such an approach - you don’t have to worry about leaving the boundaries of the array - for the outermost cells, the recursion will simply return the pre-defined 1.

Python implementaion

There is realisation of this algorithm in python:

def solve(arr, i, j):
    '''
    Recursion that returns the number 
    of ways to enrich cell i,j in a 
    board defined by arr.

    Parameters
    ----------
    arr : list of lists
        board of the task;
    i,j : int
        The coordinates of the cell for 
        which we are looking for the 
        number of paths.

    Returns
    ----------
    out : int
        number of ways to reach the 
        cell under under consideration.
    '''
    if arr[i][j]==0:
        arr[i][j]=solve(arr, i-1, j) + solve(arr, i, j-1)
    return arr[i][j]

def run(N):
    '''
    Find number of ways that allows to
    enrich cell botton right cell of board
    with size NxN from the top left cell
    of the board

    Parameters
    ----------
    N : int
        number of columns and rows 
        on the that we are solving 
        the problem for.

    Returns
    ----------
    out : int
        number of ways to reach the top
        left cell from the bottom right cell.
    '''
    arr = [
        [ (1 if (i==0 or j==0) else 0) for i in range(N)] 
        for j in range(N)
    ]
    return solve(arr, N-1, N-1)

So now we calculate the number of ways for different board sizes:

for i in range(1, 10):
    print(f"board{i}x{i} - number of pathes {run(i)}")

board1x1 - number of pathes 1
board2x2 - number of pathes 2
board3x3 - number of pathes 6
board4x4 - number of pathes 20
board5x5 - number of pathes 70
board6x6 - number of pathes 252
board7x7 - number of pathes 924
board8x8 - number of pathes 3432
board9x9 - number of pathes 12870

Robot task 2

Problem statement

This is a slightly modified version of the task from the previous section. We still have a robot that is in the top left cell of the board and wants to reach the bottom left cell of the board. The robot can still only move to the right and down. But now each cell has a cost to stay in. So our task is to come up with an algorithm that returns the lowest cost.

For example lets take board:

[1] [3] [4] [7]
[3] [7] [1] [1]
[9] [2] [1] [3]

The ceapest path will be:

[→] [→] [↓] [ ]
[ ] [ ] [↓] [ ]
[ ] [ ] [→] [ ]

And it will cost 13 points.

Solution is just like in Robot task 1 task. We will create an array that contains minimum cost for each cell. The core element of the solution is a recursive function that uses itself for cell i,j to compute the minimum between cells i-1,j and i,j-1, and fills the minimum cost array with the value obtained.

Boundary conditions

To take into account the boundary conditions, we will use the same trick as in the simpler variations of this problem. For the leftmost column, we will calculate the cost before recursion as the sum of the previous elements in that column. The same for the top row.

The followng cell implements this idea:

def fill_borders(board, path_costs):
    '''
    Fills costs for boundry column and row.

    Parameters
    ----------
    board : list of lists
        square array that for each cell define
        cost of the cell;
    path_costs : list of lists
        square array where values will be changed;
    '''
    height = len(board)
    width = len(board[0])
    
    top_border_sum = 0
    for j in range(width): 
        top_border_sum += board[0][j]
        path_costs[0][j] = top_border_sum
    left_border_sum = 0
    for i in range(height):
        left_border_sum += board[i][0]
        path_costs[i][0] = left_border_sum

Let’s see what we got:

board = [
    [1,3,4],
    [3,7,1],
    [9,2,1]
]

height = len(board)
width = len(board[0])
path_costs = [
    [None for j in range(width)]
    for i in range(height)
]
fill_borders(board, path_costs)
for l in path_costs:
    print(l)

[1, 4, 8]
[4, None, None]
[13, None, None]

Recursive function

Here is an implementation of the central function of the solution:

def solve(board, pos, path_costs):
    '''
    Recursive function that will return
    cost of path from top left cell of the board
    to selected cell. And modify array with
    lowest costs if needed.

    Parameters
    ----------
    board : list of lists
        square array that for each cell define
        cost of the cell;
    pos : tuple of 2 ints
        define the cell for which you want to 
        to calculate the cost of the route;
    path_costs : list of lists
        square array in which the already calculated 
        paths are stored;
    '''
    
    i,j=pos[0],pos[1]
    if path_costs[i][j] is not None:
        return path_costs[i][j]
    top_cost = solve(board, (i-1, j), path_costs)
    left_cost = solve(board, (i, j-1), path_costs)
    path_costs[i][j] = min(top_cost, left_cost) + board[i][j]
    return path_costs[i][j]

Let’s try the code from the previous cell. Just for random board for cell (2,2) call function. You can make sure that the function works correctly if you trace the sequence of cells with the minimum path cost from cell (2,2) to cell (0,0).

from IPython.display import HTML
from random import randint

height=7;width=10
board = [
    [randint(0, 20) for j in range(width)]
    for i in range(height)
]

display(HTML("<p style='font-size:15px'>Board</p>"))
display(board)

path_costs = [
    [None for j in range(width)]
    for i in range(height)
]
fill_borders(board, path_costs)
solve(board, (2, 2), path_costs)

display(HTML("<p style='font-size:15px'>Paths costs</p>"))
display(path_costs)

Board

[[11, 1, 19, 13, 18, 4, 4, 12, 16, 5],
 [13, 20, 6, 4, 12, 10, 9, 10, 9, 5],
 [13, 15, 10, 6, 16, 16, 17, 9, 4, 17],
 [17, 7, 12, 7, 2, 6, 9, 12, 6, 5],
 [7, 18, 19, 3, 6, 11, 16, 12, 14, 19],
 [18, 7, 7, 20, 13, 19, 6, 2, 15, 5],
 [12, 20, 12, 6, 11, 4, 7, 7, 19, 4]]

Paths costs

[[11, 12, 31, 44, 62, 66, 70, 82, 98, 103],
 [24, 32, 37, None, None, None, None, None, None, None],
 [37, 47, 47, None, None, None, None, None, None, None],
 [54, None, None, None, None, None, None, None, None, None],
 [61, None, None, None, None, None, None, None, None, None],
 [79, None, None, None, None, None, None, None, None, None],
 [91, None, None, None, None, None, None, None, None, None]]

def min_path(board):
    '''
    Function that compute cost of the cheapest
    path from top left cell of the given board
    to the bottom right cell of the given

    Parameters
    ----------
    board : list of lists
        square array that for each cell define
        cost of the cell;

    Returns
    ----------
    out : number
        cost of the cheapest path. 
    '''
    height = len(board)
    width = len(board[0])

    path_costs = [
        [None for j in range(width)]
        for i in range(height)
    ]
    fill_borders(board, path_costs)
    return solve(board, (height-1, width-1), path_costs)

Let’s try it on the obvious case - where there is a path that containing only ones.

board = [
    [1, 1, 1, 5],
    [1, 3, 1, 1],
    [3, 1, 5, 1]
]
min_path(board)

6