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

# Problem statement

Given two strings, find the length of the longest common subsequence between them. A common subsequence in a pair of strings is a sequence that follows the same order of characters, but the sequence does not necessarily have to be contiguous. For example, two strings `two` and `too` have a common subsequence of `to`. Even though `to` does not appear contiguously in `two`, the order of characters is still preserved, i.e., `o` follows `t`. While these strings had smaller subsequences as well, such as `t` and `o`, in the context of this problem, we are only interested in finding the length of the longest subsequence.

# Input

Your algorithm will take two strings, i.e., `str1` and `str2`, as input. Strings can be of variable length, even empty too.


```
str1 = "two"
str2 = "too"
```

# Output

Your algorithm should return an integer representing the length of the longest common subsequence.

```
LCS("two", "too") = 2
``` 

# Problem statement

You have already solved a similar problem of the [longest common substring](https://www.educative.io/courses/dynamic-programming-in-python/solution-review-longest-common-substring) in the previous chapter. This problem is slightly different because we are finding subsequence instead of substring here. Think about a simple recursive solution first and then build on that to write a dynamic programming solution. Best of luck!

In this lesson, we will look at another classic dynamic programming problem: the longest common subsequence 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

Challenge: Longest Common Subsequence

Problem statement