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 a string, find the length of the longest common palindromic subsequence in that string. Let’s first review what a palindrome is. A **palindrome** is a sequence that reads the same in either direction. For example, `madam` is a famous palindromic string. If you read it from start to end or from end to start, it reads the same.


As we have seen in the last challenge, unlike substring, subsequence does not have to be contiguous. So, in a string, `racer car`, we may not have any palindromic substring of length greater than one, but we have a few palindromic subsequences. For example, `cec`, `aceca`, or the longest of them all `racecar`.

So, you need to find the length of the longest palindromic subsequence.

# Input

Your algorithm will take a string of variable length as input.

```
str = "racercar"
```

# Output

Your algorithm should return an integer value representing the length of the longest palindromic subsequence in the given string.

```
LPS("racercar") = 7
```

# Coding challenge

This problem builds on the problem of the [longest common subsequence](https://www.educative.io/courses/dynamic-programming-in-python/solution-review-longest-common-subsequence) we discussed in the last lesson. Try to think about how you can define this problem in terms of the longest common subsequence problem. We have provided the function to find the length of the longest common subsequence below. You may use this function in your solution. If you are able to figure out the relation of this problem with the longest common subsequence problem, it is a really easy problem. So, think carefully and then write the code. Best of luck!

In this lesson, we will build on the problem from the last coding challenge to solve another interesting 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 Palindromic Subsequence

Problem statement