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

## Solution: Using longest common subsequence function

def LCS(str1, str2):
    n = len(str1)   # length of str1
    m = len(str2)   # length of str1

    dp = [0 for i in range(n+1)]  # table for tabulation, only maintaining state of last row

    for j in range(1, m+1):           # iterating to fill table
        thisrow = [0 for i in range(n+1)] # calculate new row (based on previous row i.e. dp)
        for i in range(1, n+1):
            if str1[i-1] == str2[j-1]:    # if characters at this position match, 
                thisrow[i] = dp[i-1] + 1 # add 1 to the previous diagonal and store it in this diagonal
            else:
                thisrow[i] = max(dp[i], thisrow[i-1]) # if character don't match, use i-th result from dp, and previous result from thisrow
        dp = thisrow   # after evaluating thisrow, set dp equal to this row to be used in the next iteration
    return dp[n]

from lcs import LCS
# call longest common subsequence function as follows: 
#   LCS(str1, str2)
#   returns integer for length of the longest common subsequence in str1 and str2

def LPS(str):
    return LCS(str, str[::-1])

print(LPS("racercar"))

### Explanation

That's it. All the magic happens in the `LCS` function and we have already seen how that function works in the [previous solution review](https://www.educative.io/courses/dynamic-programming-in-python/solution-review-longest-common-subsequence). We have simply called the `LCS` function with the actual string `str` and its reversed form `str[::-1]`. Let's see why this works.

We know that we wrote our `LCS` algorithm to compare characters from the start of the strings towards the end. In this case, we want to compare the same string starting from the opposite ends. One way to exploit our implementation of `LCS` is to simply pass it the original string and its reversed version.


### Time and space complexity

Time taken in reversing a string is *O(n)*, while we know that `LCS` has a time complexity of *O(nm)* given strings of sizes *n* and *m*. Since here we have two versions of the same string, they will have the same length, *n*.  Thus, the time complexity would be **O(n$^2$)**. Similarly, the space complexity would also be **O(n$^2$)**.

## Longest palindromic substring

While we're at it, let's look at another almost identical problem. Given a string, find the longest palindromic substring in it. Remember the difference between subsequence and substring: **substring** is a contiguous part of a string while **subsequence** doesn't necessarily have to be contiguous. You can take a look at the problem of the [longest common substring](https://www.educative.io/courses/dynamic-programming-in-python/solution-review-longest-common-substring) that we solved in the previous chapter. 

Even though the problems look similar, they don’t have similar solutions. Here is an implementation for this problem, which clearly gives the wrong answer.

# Solution: Using longest common subsequence function

## Explanation

That's it. All the magic happens in the `LCS` function and we have already seen how that function works in the [previous solution review](https://www.educative.io/courses/dynamic-programming-in-python/solution-review-longest-common-subsequence). We have simply called the `LCS` function with the actual string `str` and its reversed form `str[::-1]`. Let's see why this works.

We know that we wrote our `LCS` algorithm to compare characters from the start of the strings towards the end. In this case, we want to compare the same string starting from the opposite ends. One way to exploit our implementation of `LCS` is to simply pass it the original string and its reversed version.


## Time and space complexity

Time taken in reversing a string is *O(n)*, while we know that `LCS` has a time complexity of *O(nm)* given strings of sizes *n* and *m*. Since here we have two versions of the same string, they will have the same length, *n*.  Thus, the time complexity would be **O(n$^2$)**. Similarly, the space complexity would also be **O(n$^2$)**.

# Longest palindromic substring

While we're at it, let's look at another almost identical problem. Given a string, find the longest palindromic substring in it. Remember the difference between subsequence and substring: **substring** is a contiguous part of a string while **subsequence** doesn't necessarily have to be contiguous. You can take a look at the problem of the [longest common substring](https://www.educative.io/courses/dynamic-programming-in-python/solution-review-longest-common-substring) that we solved in the previous chapter. 

Even though the problems look similar, they don’t have similar solutions. Here is an implementation for this problem, which clearly gives the wrong answer.

In this lesson, we will see the solution to the longest palindromic subsequence problem and see another similar problem to the longest palindromic 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

Solution Review: Longest Palindromic Subsequence