Gain insights into dynamic programming, explore recursion basics, and delve into advanced techniques like Bottom-Up optimization. Discover ways to solve complex problems more efficiently with hands-on coding challenges.

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.

Dynamic Programming in Python: Optimizing Programs for Efficiency

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 it 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):

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

# Explanation

Let’s break down what we did there. The basic idea is to place the queen at all possible positions to find out what fits our needs. We start off placing a queen in the first row’s first box and then make a recursive call to place a queen in the second row. Here we place a queen in a safe position and check recursively again for the next rows. If any of the recursive calls return false, we check the next box on the previous row, and so on.


Look at the visualization of a dry run on an example where `n = 4`.



Observe how simple and intuitive this solution is. All we are doing is placing queens in a row and checking whether, after placing that queen, we can place queens in proceeding rows. Now if you look at the code, start with *line 20*, where we iterate over the `r`$^{th}$ row and see which box is safe to place a queen (*line 21*). When we find such a box, we update its value (*line 23*) and make a recursive call to check for proceeding rows (*line 24*). If this recursive call returns `True`, this means all `n` queens have been placed and we should return `True` as well (*lines 26-27*). Otherwise, we need to revert the queen we placed (*line 29*) and continue checking for the rest of the boxes in `r`$^{th}$ row. If no box is suitable, we return `False`.

Now, let's come to our base case. Since we are going row by row, when we have placed queens safely in `n` rows, we do not need to do anything further. This is our base case, given in *lines 17-18*.

# Time complexity

This algorithm has a pretty high time complexity: **O(n$^n$)**. Think about the solution space. In the first row you can place a queen at `n` places. For each of these `n` options, you have the option to place a queen at `n` more in the second row, and so on up to `n`. Therefore:

$n \times n \times n$ ... $\times n = n^n$

Plug in a slightly bigger number (~20) in the code playground above and see how the response time changes.

---

This was it for simple recursion, but don't worry, because we will be working on even more recursion problems in later chapters. In the next lesson, we will look at why recursion alone is not enough.



In this lesson, we will go over the solution to the challenge from the previous lesson.


Chapter 1: From Recursion to Dynamic Programming

Chapter 2: Top-Down Dynamic Programming with Memoization

Chapter 3: Bottom-Up Dynamic Programming with Tabulation

Chapter 4: Practice Problems

Solution Review: Place N Queens on an NxN Chessboard

Solution #

Explanation