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

Given two strings, we want to find the length of the longest substring common in both these strings. For example, if we have two strings, `"hello elf"` and `"hello yourself"`, we can see two prominent substrings: `"hello "` and `"elf"`. Since `"hello "` is longer, this will be the longest common substring for the given pair of strings.

# Input

Your program will take two strings, `str1` and `str2`, each of length greater than zero as input.


```
str1 = "hello elf"
str2 = "hello yourself"
```


# Output

Your program should return the length of the longest common substring. 

```
lcs("hello elf", "hello yourself") = 6
lcs("hel", "elf") = 2
```

# Coding challenge

Think about some basic examples to start with and then write a simple recursive algorithm. Slowly build up to the bottom-up solution.

You may check your recursive algorithm by setting `stressTesting` to `False`. Similarly to check only top-down implementation, set `testForBottomUp` to `False`. Best of luck!



In this lesson, you will work on an interesting dynamic programming problem, the longest common substring.


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 2: Longest Common Substring

Problem statement