Dynamic Programming in Python: Optimizing Programs for Efficiency Educative Quiz Answers

Get Dynamic Programming in Python: Optimizing Programs for Efficiency Educative Quiz Answers

Dynamic programming is something every developer should have in their toolkit. It allows you to optimize your algorithm with respect to time and space — a very important concept in real-world applications.

In this course, you’ll start by learning the basics of recursion and work your way to more advanced DP concepts like Bottom-Up optimization. Throughout this course, you will learn various types of DP techniques for solving even the most complex problems. Each section is complete with coding challenges of varying difficulty so you can practice a wide range of problems.

By the time you’ve completed this course, you will be able to utilize dynamic programming in your own projects.

Enroll on Educative

Challenge 1: Find All Permutations of a String

Answer:

def permutations(str):
  if str == "": # base case
    return [""]
  permutes = []
  for char in str:
    subpermutes = permutations(str.replace(char, "", 1))    # recursive step
    for each in subpermutes:
      permutes.append(char+each)
  return permutes

Challenge 2: Place N Queens on an NxN Chessboard

Answer:

def isSafe(i, j, board):
  for c in range(len(board)):
    for r in range(len(board)):
      # check if i,j share row with any queen
      if board[c][r] == 'q' and i==c and j!=r: 
        return False
      # check if i,j share column with any queen
      elif board[c][r] == 'q' and j==r and i!=c:
        return False
      # check if i,j share diagonal with any queen
      elif (i+j == c+r or i-j == c-r) and board[c][r] == 'q':
        return False
  return True 

def nQueens(r, n, board):
  # base case, when queens have been placed in all rows return
  if r == n:
    return True, board
  # else in r-th row, check for every box whether is is suitable to place queen
  for i in range(n):
    if isSafe(r, i, board):
      # if i-th columns is safe to place queen, place the queen there and check recursively for other rows
      board[r][i] = 'q'
      okay, newboard = nQueens(r+1, n, board)
      # if all next queens were placed correctly, recursive call should return true, and we should return true here too
      if okay:
        return True, newboard
      # else this is not a suitable box to place queen, and we should check for next box
      board[r][i] = '-'
  return False, board

def placeNQueens(n, board):

  '''
  To check whether index i,j is safe to place queen call isSafe(i, j, board)
  True means it is safe, False means it is not
  '''
  return nQueens(0, n, board)[1]

def main():
  n = 4
  board = [["-" for _ in range(n)] for _ in range(n)]
  qBoard = placeNQueens(n, board)
  qBoard =  "\n".join(["".join(x) for x in qBoard])
  print (qBoard)
main()

Quiz 1: From Recursion to Dynamic Programming

Q1.

def func(num):
    if num <= 0:
        return 0
    elif num % 2 == 0:
        return num + func(num - 2)
    else:
        return num + func(num - 1) + 1

func function employs binary recursion

• True
• False

Q2.

def func(num):
    return func(num - 1) + num

What would func(5) return:

• 15
• 0
• Recursion Error

Q3.

def func(str):
    if len(str) >= 1:
        print(str[0])
        func(str[1:])
    

What kind of recursion is this? (you can select multiple correct answers)

• Head recursion
• Tail recursion
• Binary recursion
• Linear recursion

Q4. Simple recursion is more related to which of the following words?

• Brute-force
• Optimized
• Efficient
• Incorrect

Q5. All the algorithms that use loops can be converted into recursive algorithm

• True
• False

Q6. Recursion is more similar to which of the following two approaches:

• Top-down
• Bottom-up

Q7. After employing principles of dynamic programming, the Fibonacci numbers’ algorithm’s complexity drops from exponential to:

• Quadratic
• Logarithmic
• Linear
• Linearithmic

Q8. Identify the scenario where dynamic programming is more likely to work.

• A problem depends on different subproblems, but overlap of subproblems is small
• A problem depends on subproblems but optimal solution may not be built using the optimal solution to subproblems.
• Optimal solution of the problem can be constructed using optimal solution of subproblems but overlap of subproblems is small
• A problem depends on different subproblems and overlap of subproblem is significant

Q9. Finding all permutations of a string has which of the following properties:

(you can select multiple correct answers)

• Optimal substructure
• Overlapping subproblem
• None

Challenge 3: The Staircase Problem

Answer:

def nthStair(n, m, memo):
  if n == 0:    # base case of when there is no stair
    return 1
  if n in memo: # before recursive step check if result is memoized
    return memo[n]
  ways = 0
  for i in range(1,m+1):    # iterate over number of steps, we can take
    # if steps remaining is smaller than the jump step, skip 
    if i <= n:              
      #recursive call with n i units lesser where i is the number of steps taken here
      ways += nthStair(n-i, m, memo) 
  # memoize result before returning
  memo[n] = ways   
  return ways

def staircase(n, m):
  memo = {}
  # helper function to add memo dictionary to function
  return nthStair(n, m, memo) 

Challenge 4: The Knapsack Problem

Answer:

def solveKnapsack(weights, prices, capacity, index, memo):
  # base case of when we have run out of capacity or objects
  if capacity <= 0 or index >= len(weights): 
    return 0
  # check for solution in memo table
  if (capacity, index) in memo: 
    return memo[(capacity, index)]
  # if weight at index-th position is greater than capacity, skip this object
  if weights[index] > capacity: 
    # store result in memo table
    memo[(capacity, index)] = solveKnapsack(weights, prices, capacity, index + 1, memo) 
    return memo[(capacity, index)] 
  # recursive call, either we can include the index-th object or we cannot, we check both possibilities and return the most optimal one using max
  memo[(capacity, index)] = max(prices[index]+solveKnapsack(weights, prices, capacity - weights[index], index+1, memo),
        solveKnapsack(weights, prices, capacity, index + 1, memo)) 
  return memo[(capacity, index)]

def knapsack(weights, prices, capacity):
  # create a memo dictionary
  memo = {} 
  return solveKnapsack(weights, prices, capacity, 0, memo)

Quiz 2: Top-Down Dynamic Programming with Memoization

Q1. Dynamic programming can reduce the time complexity of all exponential algorithms.

• True
• False

Q2. Dynamic programming reduces the time complexity of all the exponential algorithms that obey the properties of optimal substructure and overlapping subproblems to linear time.

• True
• False

Q3. In the knapsack problem, time complexity is not linear even after memoization.

• True
• False

Q4. Top down dynamic programming consists of:

You can select multiple correct options.

• Base case
• Recursive step
• Memoization
• None of the above

Q5. What could be potential limitation(s) of memoization?

You can select multiple correct options.

• Memory
• Problem’s complexity
• Runtime
• Programming language

Q6. What is time complexity of this algorithm:

def fib(n, memo):
 if n <= 1:
   return 1
 elif n in memo:
   return memo[n]
 else:
   return fib(n-1, memo) + fib(n-2, memo)

• O(n)
• O(n^2)
• O(2^n)
• O(nlogn)

Q7. In top down approach:

• subproblems are evaluated before the main problem
• main problem is evaluated before the subproblems

Q8. In top down approach:

• Call is made to the subproblems before the main problem.
• Call is made to the main problem before the subproblem.

Challenge 5: The Catalan Numbers

Answer:

def catalan(n):
  table = [None] * (n+1)  # tabulating 
  table[0] = 1            # handling the base case
  for i in range(1,n+1):  # iterating to fill up the tabulation table
    table[i] = 0          # initializing the i-th value to 0
    for j in range(i):    # iterate from 0 to i; according to formula of catalan i.e. C0*Ci + C1*Ci-1 + ... Ci*C0
      table[i] += (table[j] * table[i-j-1]) # C(j) * C(i-j-1)
  return table[n]         

stressTesting = True  # to only check if your recursive solution is correct, set it to false
testForBottomUp = True   # to test a top down implementation set it to false    

Challenge 6: Longest Common Substring

Answer:

def lcs(str1, str2):
  n = len(str1)   # length of str1
  m = len(str2)   # length of str1

  dp = [[0 for j in range(m+1)] for i in range(n+1)]  # table for tabulation of size m x n
  maxLength = 0   # to keep track of longest substring seen 

  for i in range(1, n+1):           # iterating to fill table
    for j in range(1, m+1):
      if str1[i-1] == str2[j-1]:    # if characters at this position match, 
        dp[i][j] = dp[i-1][j-1] + 1 # add 1 to the previous diagonal and store it in this diagonal
        maxLength = max(maxLength, dp[i][j])  # if this substring is longer, replace it in maxlength
      else:
        dp[i][j] = 0 # if character don't match, common substring size is 0
  return maxLength

stressTesting = True  # to only check if your recursive solution is correct, set it to false
testForBottomUp = True   # to test a top down implementation set it to false    

Quiz 3: Bottom-Up Dynamic Programming with Tabulation

Q1. What edge does bottom-up dynamic programming have over top-down dynamic programming?

• More stack memory consumption
• More intuitive
• Better space complexity
• No overhead of return statements

Q2. By using tabulation instead of memoization, we can improve our algorithm’s space complexity.

• True
• False

Q3. Similar to Fibonacci numbers, space complexity of Catalan’s numbers can be reduced to O(1).

• True
• False

Q4. We cannot reduce the space complexity of the Fibonacci numbers algorithm to O(1) if we use the top-down approach.

• True
• False

Q5. We have two strings, str1 and str2, of varied sizes. What would be the space complexity of an efficient algorithm to compute the length of the longest common substring?

• O(length of str1)
• O(length of str1)
• O(min(length of str1, length of str2))
• O(max(length of str1, length of str2))

Challenge 7: Number of Ways to Represent N Dollars

Answer:

def countways(bills, amount):
  if amount <= 0:
    return 0
  dp = [[1 for _ in range(len(bills))] for _ in range(amount + 1)]
  for amt in range(1, amount+1):
    for j in range(len(bills)):
      bill = bills[j]
      if amt - bill >= 0:
        x = dp[amt - bill][j]
      else:
        x = 0
      if j >= 1:
        y = dp[amt][j-1]
      else:
        y = 0
      dp[amt][j] = x + y
  return dp[amount][len(bills) - 1]

Challenge 8: The Rod Cutting Problem

Answer:

def rodCutting(n, prices):
  # Create a dp array the size of (n+1)
  dp = [0 for _ in range(n + 1)]  
  # starting from rod of length 1, find optimal answer to all subproblems
  for i in range(1, n + 1):       
    max_val = 0
    # for a rod of length i, we can find what cuts give max answer since we have answer to all smaller cuts
    for j in range(i):            
      max_val = max(max_val, prices[j]+dp[i-j-1])
    dp[i] = max_val
  # return answer to n length rod
  return dp[n]                    

stressTesting = True

Challenge 9: Weighted Scheduling Problem

Answer:

# Given the index of the class and the list of schedule, this function returns the last class that does not conflict with this class, if it exists otherwise returns None
def lastConflict(index, schedule, isSorted = False):
  if not isSorted:
    schedule = sorted(schedule, key=lambda tup: tup[1])
  for i in range(index, -1, -1):
    if schedule[index][0] >= schedule[i][1]:
      return i
  return None

def WeightedSchedule(schedule):
  schedule = sorted(schedule, key=lambda tup: tup[1])
  dp = [0 for _ in range(len(schedule)+1)]

  for i in range(1, len(schedule)+1):
    index_LC = lastConflict(i-1, schedule, isSorted=True)
    if index_LC == None:
      index_LC = -1
    dp[i] = max(dp[i-1], dp[index_LC+1]+schedule[i-1][2])
  return dp[len(schedule)]

stressTesting = True

Challenge 10: The Matrix Chain Multiplication

Answer:

import numpy as np

def minMultiplications(dims):    
    dp = [[0 for _ in range(len(dims))] for _ in range(len(dims))]

    for l in range(2,len(dims)):
        for i in range(1,len(dims)-l+1):
            j = i+l-1
            dp[i][j] = np.inf
            for k in range(i, j):
                temp = dp[i][k]+ dp[k+1][j] + dims[i-1]*dims[k]*dims[j]
                if temp < dp[i][j]:
                    dp[i][j] = temp
    return dp[1][-1]
    

Challenge 11: The Traveling Salesman Problem

Answer:

import numpy as np

def findSubsets(numbers, i, subsets):
	if len(numbers) == i:
		return subsets
	if len(subsets) == 0:
		return findSubsets(numbers, i+1, [(), tuple([numbers[i]])])
	temp_subsets = []
	for subset in subsets:
		temp_subsets += [tuple(list(subset) + [numbers[i]])]
	return findSubsets(numbers, i+1, subsets + temp_subsets)
  
# function to find shortest path starting from city `start` and back to it
def TSPbottomup(distances, start):
  dp = {} # dp table
  # subproblem of travelling to second city from start city
  for i in range(len(distances)):
    dp[(tuple([i]), i)] = distances[start][i]
  # find all possible subsets of the cities
  subsets = findSubsets(list(range(len(distances))), 0, [])
  # solve for subset of each size from 2 to n
  for subsetSize in range(2,len(distances)+1):
    for subset in subsets:
      if len(subset) == subsetSize:
        # evaluating minimum cost to travel `subsetSize` number of cities while ending up at each city 
        for lastCity in subset:
          dp[(subset, lastCity)] = np.inf
          l = list(subset)
          l.remove(lastCity)
          subset2 = tuple(l)
          # to end up at city given by `lastCity`, it should be the last city to be travelled
          for city in subset2:
            dp[(subset, lastCity)] = min(dp[(subset, lastCity)], dp[(subset2, city)] + distances[city][lastCity])
  # return answer to the problem of travlling all cities while ending up at start city
  return dp[(subsets[-1], start)]

def TSP(distances):
  minimum = np.inf
  for i in range(len(distances)):
    minimum = min(minimum, TSPbottomup(distances, i))
  return minimum

stressTesting = True

Challenge 12: Longest Common Subsequence

Answer:

def LCS(str1, str2):
    n = len(str1)   # length of str1
    m = len(str2)   # length of str1

    dp = [[0 for j in range(m+1)] for i in range(n+1)]  # table for tabulation of size m x n
    
    # iterating to fill table
    for i in range(1, n+1):           
        for j in range(1, m+1):
            # if characters at this position match, 
            if str1[i-1] == str2[j-1]:    
                # add 1 to the previous diagonal and store it in this diagonal
                dp[i][j] = dp[i-1][j-1] + 1 
            else:
                # if character don't match, take max of last two positions vertically and horizontally
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 
    return dp[n][m]

stressTesting = True

Challenge 13: Longest Palindromic Subsequence

Answer:

from lcs import LCS
# call longest common subsequence function as follows: 
#   LCS(str1, str2)
#   returns integer for length of the longest common subsequence in str1 and str2

def LPS(str):
    return LCS(str, str[::-1])

Challenge 14: The Edit Distance Problem

Answer:

def editDistance(str1, str2):
    n = len(str1)
    m = len(str2)

    dp = [[0 for j in range(m+1)] for i in range(n+1)]

    for i in range(n+1):
        for j in range(m+1):
            if i == 0:
                dp[i][j] = j
            elif j == 0:
                dp[i][j] = i
            elif str1[i-1] == str2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j-1],
                                   dp[i][j-1],
                                   dp[i-1][j])
    return dp[n][m]

Conclusion:

I hope this Dynamic Programming in Python: Optimizing Programs for Efficiency Educative Quiz Answers would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions