DSA 28: Dynamic Programming [Part 1]

1. Max Value (No DP Technique)

def max_val(arr):
    if len(arr)==1:
        return arr[0]
    if arr[0]>max_val(arr[1:]):
        return arr[0]
    return max_val(arr[1:])

max_val([1,8,5,7,3,6])

8

1.1 Repeated Recursive Calls: with print()

Without any dynamic programming techniques, the function runs uncessarily slow:

• repeated and unncessary calls to obtain calculated previously calculated max values:
  • These values were calculated used for the comparison then disregarded
• max_val_no_dp(4) is called 14-times!
• Time-complexity: \[O(2^n)\]

def max_val_no_dp(arr):
    print(f"max_val_no_dp called on: {arr}")
    if len(arr)==1:
        return arr[0]
    if arr[0]>max_val_no_dp(arr[1:]):
        return arr[0]
    return max_val_no_dp(arr[1:])

max_val_no_dp([1,2,3,4])

max_val_no_dp called on: [1, 2, 3, 4]
max_val_no_dp called on: [2, 3, 4]
max_val_no_dp called on: [3, 4]
max_val_no_dp called on: [4]
max_val_no_dp called on: [4]
max_val_no_dp called on: [3, 4]
max_val_no_dp called on: [4]
max_val_no_dp called on: [4]
max_val_no_dp called on: [2, 3, 4]
max_val_no_dp called on: [3, 4]
max_val_no_dp called on: [4]
max_val_no_dp called on: [4]
max_val_no_dp called on: [3, 4]
max_val_no_dp called on: [4]
max_val_no_dp called on: [4]

4

1.2 Repeated Recursive Calls: Chart

2. Memoization

By setting the most recent call of max_val_memo to a variable max_val_remainder:

• The function can recall previous max value at O(1)
• max_val_memo(4) is called 4-times only
• Avoiding repeated and unncessary calls
• Time-complexity: \[O(N)\]

This is a variation of the Dynamic Programming technique called Memoization!

By using memoization, our time-complexity reduced from:

• \(O(2^N)\to O(N)\)

Amazing 🥂!

def max_val_memo(arr):
    print(f"max_val_memo called on: {arr}")
    if len(arr)==1:
        return arr[0]
    max_val_remainder = max_val_memo(arr[1:])
    # if arr[0]>max_val_memo(arr[1:]):
    if arr[0]>max_val_remainder:
        return arr[0]
    return max_val_remainder

max_val_memo([1,2,3,4])

max_val_memo called on: [1, 2, 3, 4]
max_val_memo called on: [2, 3, 4]
max_val_memo called on: [3, 4]
max_val_memo called on: [4]

4