Chapter 2 - Dynamic Programming

Question 1

Longest Common Subsequence

Answer 1

Brute Force:
Given two texts text1 and text2, we can try possible subsequences of both to find max.
Match text1[i] and text2[j], and then recursively match the remaining substring
Complexity: O(2^[m+n]) & O(m+n) -> time and space, m and n are lengths of text1 and text2

Dp solution:
Use a 2d dp array to store the subproblems already solved.

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        memo = [[-1 for _ in range(len(text2))] for _ in range(len(text1))]
        return self.longestCommonSubsequence_recursive(memo, text1, text2, 0, 0)

def longestCommonSubsequence_recursive(self, memo, text1, text2, i, j):
    if i == len(text1) or j == len(text2):
        return 0
    if memo[i][j] == -1:
        if text1[i] == text2[j]:
            memo[i][j] = 1 + self.longestCommonSubsequence_recursive(memo, text1, text2, i + 1, j + 1)
        else:
            memo[i][j] = max(self.longestCommonSubsequence_recursive(memo, text1, text2, i + 1, j),
                             self.longestCommonSubsequence_recursive(memo, text1, text2, i, j + 1))
    return memo[i][j]

Complexity: O(n*m)

Question 2

Longest Palindromic Subsequence

Input: “bbbab”
Output: 4
One possible longest palindromic subsequence is “bbbb”.

Input: “cbbd”
Output: 2
One possible longest palindromic subsequence is “bb”.

Answer 2

Brute Force:
Two pointers, one from beginning and other from the end, compare the two letters, if they are same, check for the remaining substring.
If they are not same, run it recursively for max of moving the start pointer by 1 and moving the end pointer back by 1
Complexity: O(2^n) & O(N) -> time and space

Dp solution:
Store all the calculated subsequences in a 2d DP array

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        memo = [[-1 for _ in range(len(s))] for _ in range(len(s))]
        return self.longestPalindromeSubseq_recursive(memo, s, 0, len(s) - 1)

    def longestPalindromeSubseq_recursive(self, memo, s, start, end):
        if start > end:
            return 0

        # every sequence with one element is a palindrome of length 1
        if start == end:
            return 1

    if memo[start][end] == -1:
        # case 1: elements at the beginning and the end are the same
        if s[start] == s[end]:
            memo[start][end] = 2 + self.longestPalindromeSubseq_recursive(memo, s, start + 1, end - 1)
        else:
            # case 2: skip one element either from the beginning or the end
            subseq1 = self.longestPalindromeSubseq_recursive(memo, s, start + 1, end)
            subseq2 = self.longestPalindromeSubseq_recursive(memo, s, start, end - 1)
            memo[start][end] = max(subseq1, subseq2)

    return memo[start][end]

Complexity: O(N^2) & O(N^2) -> time and space

Question 3

Climbing Stairs:

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Answer 3

Brute Force:
If we don’t take or have any step, there is only 1 way. Similarly, if there is one stair, there is only 1 way to climb it.
If there are 2 steps, there are 2 ways to climb them.

Above are the termination conditions, now run the loop recursively for [climbStairs(n - 1) + climbStairs(n - 2) ]

Complexity: O(2^n) & O(n) -> time and space

Dp Solution:
Use a dp array to store already calculated ways

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = [0 for x in range(n+1)]
        dp[0] = 1
        dp[1] = 1

    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n]

Complexity: O(n) and O(n) -> time and space