DSA 29: Dynamic Programming - Exercises [Part 2]

1. Add Items To 100

def add_until_100(array):
    print(f"fn called: {array}")
    if not array:
        return 0
    if array[0] + add_until_100(array[1:]) > 100:
        return add_until_100(array[1:])
    else:
        return array[0] + add_until_100(array[1:])

add_until_100([1,90,2,80,3])

fn called: [1, 90, 2, 80, 3]
fn called: [90, 2, 80, 3]
fn called: [2, 80, 3]
fn called: [80, 3]
fn called: [3]
fn called: []
fn called: []
fn called: [3]
fn called: []
fn called: []
fn called: [80, 3]
fn called: [3]
fn called: []
fn called: []
fn called: [3]
fn called: []
fn called: []
fn called: [2, 80, 3]
fn called: [80, 3]
fn called: [3]
fn called: []
fn called: []
fn called: [3]
fn called: []
fn called: []
fn called: [80, 3]
fn called: [3]
fn called: []
fn called: []
fn called: [3]
fn called: []
fn called: []
fn called: [90, 2, 80, 3]
fn called: [2, 80, 3]
fn called: [80, 3]
fn called: [3]
fn called: []
fn called: []
fn called: [3]
fn called: []
fn called: []
fn called: [80, 3]
fn called: [3]
fn called: []
fn called: []
fn called: [3]
fn called: []
fn called: []
fn called: [2, 80, 3]
fn called: [80, 3]
fn called: [3]
fn called: []
fn called: []
fn called: [3]
fn called: []
fn called: []
fn called: [80, 3]
fn called: [3]
fn called: []
fn called: []
fn called: [3]
fn called: []
fn called: []

86

1.1 Add Items To 100: Tony’s Solution

Result of Memoization:

• Reduction of recursive function calls:
  • From 63 to 10 calls! (Input:n=5)

def add_until_100(array):
    print(f"fn called: {array}")
    if not array:
        return 0
    
    curr_sum = add_until_100(array[1:])
    
    if array[0] + curr_sum > 100:
        return add_until_100(array[1:])
    else:
        return array[0] + curr_sum

add_until_100([1,90,2,80,3])

fn called: [1, 90, 2, 80, 3]
fn called: [90, 2, 80, 3]
fn called: [2, 80, 3]
fn called: [80, 3]
fn called: [3]
fn called: []
fn called: [2, 80, 3]
fn called: [80, 3]
fn called: [3]
fn called: []

86

2. golomb Function

def golomb(n):
    print(f"golumn called: {n}")
    if n == 1:
        return 1

    return 1 + golomb(n - golomb(golomb(n - 1)))

golomb(5)

golumn called: 5
golumn called: 4
golumn called: 3
golumn called: 2
golumn called: 1
golumn called: 1
golumn called: 1
golumn called: 2
golumn called: 1
golumn called: 1
golumn called: 1
golumn called: 1
golumn called: 2
golumn called: 1
golumn called: 1
golumn called: 1
golumn called: 2
golumn called: 1
golumn called: 1
golumn called: 1
golumn called: 3
golumn called: 2
golumn called: 1
golumn called: 1
golumn called: 1
golumn called: 2
golumn called: 1
golumn called: 1
golumn called: 1
golumn called: 1
golumn called: 3
golumn called: 2
golumn called: 1
golumn called: 1
golumn called: 1
golumn called: 2
golumn called: 1
golumn called: 1
golumn called: 1
golumn called: 1

3

2.1 golomb Function: Tony’s Solution

I originally forgot how to create and apply the memoization with the python dictionary so I had to write fib() first, seen in 2.1.1.

Result of Memoization:

• Reduction of recursive function calls:
  • From 40 to 10 calls (Input:n=5)

def golomb(n, memo={}):
    print(f"golumn called: {n}")
    if n == 1:
        return 1
    
    if n not in memo:
        memo[n]=1 + golomb(n - golomb(golomb(n - 1)))
    
    return memo[n]

golomb(5)

golumn called: 5
golumn called: 4
golumn called: 3
golumn called: 2
golumn called: 1
golumn called: 1
golumn called: 1
golumn called: 2
golumn called: 1
golumn called: 2
golumn called: 2
golumn called: 3
golumn called: 3

3

2.1.1 fib()

def fib(n, memo={}):
    if n==1 or n==0:
        return 1
    
    if n not in memo:
        memo[n] = fib(n-2) + fib(n-1)
    
    return memo[n] 

fib(7)

21

3. Unique Paths

def unique_paths(rows, columns):
    print(f"unique_paths ran: {(rows,columns)}")
    if rows == 1 or columns == 1:
        return 1

    return unique_paths(rows - 1, columns) + unique_paths(rows, columns - 1)

unique_paths(3,4)

unique_paths ran: (3, 4)
unique_paths ran: (2, 4)
unique_paths ran: (1, 4)
unique_paths ran: (2, 3)
unique_paths ran: (1, 3)
unique_paths ran: (2, 2)
unique_paths ran: (1, 2)
unique_paths ran: (2, 1)
unique_paths ran: (3, 3)
unique_paths ran: (2, 3)
unique_paths ran: (1, 3)
unique_paths ran: (2, 2)
unique_paths ran: (1, 2)
unique_paths ran: (2, 1)
unique_paths ran: (3, 2)
unique_paths ran: (2, 2)
unique_paths ran: (1, 2)
unique_paths ran: (2, 1)
unique_paths ran: (3, 1)

10

3.1 Unique Paths: Tony’s Solution 1

Use unique string id: combining rows and columns as the key to memo dictionary.

• For example R1C2 for row 1 column 2

def unique_paths(rows, columns, memo={}):
    print(f"unique_paths ran: {(rows,columns)}")
    if rows == 1 or columns == 1:
        return 1
    uid_rc = "R"+str(rows)+"C"+str(columns)
    if uid_rc not in memo:
        memo[uid_rc] = unique_paths(rows - 1, columns) + unique_paths(rows, columns - 1)
    return memo[uid_rc]

unique_paths(3,4)

unique_paths ran: (3, 4)
unique_paths ran: (2, 4)
unique_paths ran: (1, 4)
unique_paths ran: (2, 3)
unique_paths ran: (1, 3)
unique_paths ran: (2, 2)
unique_paths ran: (1, 2)
unique_paths ran: (2, 1)
unique_paths ran: (3, 3)
unique_paths ran: (2, 3)
unique_paths ran: (3, 2)
unique_paths ran: (2, 2)
unique_paths ran: (3, 1)

10

3.2 Unique Paths: Tony’s Solution 2

Use tuple: combining rows and columns as the key to memo dictionary.

• For example (1,2) for row 1 column 2

def unique_paths(rows, columns, memo={}):
    print(f"unique_paths ran: {(rows,columns)}")
    if rows == 1 or columns == 1:
        return 1
    if (rows,columns) not in memo:
        memo[(rows,columns)] = unique_paths(rows - 1, columns) + unique_paths(rows, columns - 1)
    return memo[(rows,columns)]

unique_paths(3,4)

unique_paths ran: (3, 4)
unique_paths ran: (2, 4)
unique_paths ran: (1, 4)
unique_paths ran: (2, 3)
unique_paths ran: (1, 3)
unique_paths ran: (2, 2)
unique_paths ran: (1, 2)
unique_paths ran: (2, 1)
unique_paths ran: (3, 3)
unique_paths ran: (2, 3)
unique_paths ran: (3, 2)
unique_paths ran: (2, 2)
unique_paths ran: (3, 1)

10