Learn about dynamic programming in Python, delve into recursion basics, explore advanced DP techniques, and discover practical coding challenges to optimize algorithms for real-world applications.

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

# Problem statement


You are given a map that has $n$ cities on it. All of the cities are connected directly to each other via distinct routes of variable lengths. You, being a salesman, have to travel to each of these cities on a business trip. But your company wants you to be very careful with the travel expenses and wants you to spend the least amount possible. Expenditure is a function of the distance traveled, so you want to minimize the total distance traveled. Find the length of the shortest path to travel all the cities.



# Input

You will be given a 2-d matrix, `distances`, of size $n \times n$ denoting the distance between all the cities. To check the distance from $i^{th}$ city to $j^{th}$ city, you can simply do `distances[i][j]`. The matrix does not necessarily have to be symmetrical, i.e., `distances[i][j]` $\neq$ `distances[j][i]`. You can start from any city to travel around all the other cities until you come back to the same city you started traveling from. You should not visit any city twice other than the first city.

```
distances = [
      [0, 10, 20],
      [12, 0, 10],
      [19, 11, 0]
]
```

# Output

Your algorithm should return the minimum distance traveled to traverse every city; each city other than the first. The chosen city should only be traveled to once.

```
TSP(distances) = 39
```

Let's look at the following visualization for a better understanding.

In this lesson, you will solve a coding challenge on the famous traveling salesman problem.

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

Solving Sudoku and the 8-Queens Puzzle as Constraint Satisfaction

Challenge: The Traveling Salesman Problem

Problem statement

Input