304 North Cardinal St.
Dorchester Center, MA 02124

# 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

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

``````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)

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)        func(str[1:])    ``

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

• 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:

• 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

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

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

``````def catalan(n):
table = [None] * (n+1)  # tabulating
table = 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

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

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

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

``````# 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)
for i in range(index, -1, -1):
if schedule[index] >= schedule[i]:
return i
return None

def WeightedSchedule(schedule):
schedule = sorted(schedule, key=lambda tup: tup)
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])
return dp[len(schedule)]

stressTesting = True``````

#### Challenge 10: The Matrix Chain Multiplication

``````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]

``````

#### Challenge 11: The Traveling Salesman Problem

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

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

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

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