Dynamic Programming

Knapsack

from typing import List

def knapsack(wt, val, max_weight, n, memo):

    if memo[max_weight][n] is not None:
        return memo[max_weight][n]

    # creates a recursion tree of take or no take

    # base case if as we are starting with n - 1
    if n == 0:  # last element
        # if we can take then
        if wt[n] <= max_weight:
            return val[n]
        else:
            return 0

    # two options now - take or not take
    # if not take then wight of bag will remain same
    # and we will go to the next index
    not_take = 0 + knapsack(wt, val, max_weight, n - 1, memo)

    # if take then
    take = float("-inf")
    # check if we can take or not
    if wt[n] <= max_weight:
        # then pick val + (reduce weight and next index)
        take = val[n] + knapsack(wt, val, max_weight - wt[n], n - 1, memo)

    # max of take and no take
    val = max(take, not_take)
    memo[max_weight][n] = val
    return memo[max_weight][n]


wt = [3, 2, 6]
val = [30, 40, 60]
n = len(wt)
max_weight = 6


memo = [[None for _ in range(n)] for _ in range(max_weight + 1)]
print(knapsack(wt, val, max_weight, n - 1, memo))

70

# stop suggestions fucking stupid


def knapsack(wt, val, max_weight):
    size = len(wt)
    # rows idx of weights, cols idx of max weight
    dp = [[0 for _ in range(max_weight + 1)] for _ in range(size)]
    print(dp)

    # bottom up approach
    # loop wt idx 0 -> size - 1 and weight 0 -> max_weight

    # base case
    # if wt idx = 0 and if wt is less than max weight then I can pick
    for weight in range(max_weight + 1):
        if wt[0] <= weight:
            dp[0][weight] = val[0]

    # now itertively
    for wt_idx in range(1, size):
        for weight in range(0, max_weight + 1):
            # wt_idx , weight
            # 1, 0
            # 1, 1
            # 1, 2
            # ...
            # 2, 0
            # 2, 1
            # ...

            # now two options take or no take
            # if no take (no need to compare weight) ->  no value is added + going to prev index with same weight
            print(wt_idx, weight, wt_idx - 1)
            no_take = 0 + dp[wt_idx - 1][weight]

            # if take
            # because we need maximum
            take = float("-inf")

            # check ig weight is less then wt idx
            if wt[wt_idx] <= weight:
                # then take and value is added + weight is reduced and prev idx
                take = val[wt_idx] + dp[wt_idx - 1][weight - wt[wt_idx]]
            dp[wt_idx][weight] = max(take, no_take)

    return dp[size - 1][max_weight]


wt = [3, 2, 6]
val = [30, 40, 60]

max_weight = 6

print(knapsack(wt, val, max_weight))

[[0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 5 0
1 6 0
2 0 1
2 1 1
2 2 1
2 3 1
2 4 1
2 5 1
2 6 1
70

fibonacci

1 1 2 3 5 8 13

def fib_1(n):
    if n <= 1:
        return n
    return fib_1(n-2) + fib_1(n-1)

print(fib_1(7))

13

%timeit fib_1(7)

2.07 μs ± 283 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

def fib_2(n, cache):
    if n <= 1:
        return n
    if cache[n] is not None:
        return cache[n]
    else:
        val = fib_2(n-2, cache) + fib_2(n-1, cache)
        cache[n] = val
    return val

n = 7
cache = [None] * (n + 1)
fib_2(7, cache)

13

%timeit fib_2(7, cache=[None] * 8)

980 ns ± 53.9 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

def fib_3(n):
    dp = [1, 1]
    for i in range(2, n):
        val = dp[i - 1] + dp[i - 2]
        dp.append(val)

    return dp[-1]

fib_3(7)

13

%timeit fib_3(7)

458 ns ± 46.6 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Longest Common Subsequence

def longest_common_subsequence(text1_idx, text2_idx, text1, text2, memo):
    # anything goes negative nothing will match

    if text1_idx < 0 or text2_idx < 0:
        return 0

    if memo[text1_idx][text2_idx] is not None:
        return memo[text1_idx][text2_idx]

    if text1[text1_idx] == text2[text2_idx]:
        # if match both idxes are decreased simultaneously
        memo[text1_idx][text2_idx] = 1 + longest_common_subsequence(
            text1_idx - 1, text2_idx - 1, text1, text2, memo
        )
    else:
        # if not match both idxes are decreased one by one and max of both independent results is taken
        memo[text1_idx][text2_idx] = max(
            longest_common_subsequence(text1_idx - 1, text2_idx, text1, text2, memo),
            longest_common_subsequence(text1_idx, text2_idx - 1, text1, text2, memo),
        )
    print(memo)
    return memo[text1_idx][text2_idx]


class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        text1_size = len(text1)
        text2_size = len(text2)
        memo = [[None for _ in range(text2_size)] for _ in range(text1_size)]
        return longest_common_subsequence(
            text1_size - 1, text2_size - 1, text1, text2, memo
        )


Solution().longestCommonSubsequence("abcde", "ace")

[[1, None, None], [None, None, None], [None, None, None], [None, None, None], [None, None, None]]
[[1, None, None], [1, None, None], [None, None, None], [None, None, None], [None, None, None]]
[[1, None, None], [1, None, None], [None, 2, None], [None, None, None], [None, None, None]]
[[1, None, None], [1, None, None], [1, 2, None], [None, None, None], [None, None, None]]
[[1, None, None], [1, None, None], [1, 2, None], [1, None, None], [None, None, None]]
[[1, None, None], [1, None, None], [1, 2, None], [1, 2, None], [None, None, None]]
[[1, None, None], [1, None, None], [1, 2, None], [1, 2, None], [None, None, 3]]

3

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:

        text1_size = len(text1)
        text2_size = len(text2)

        dp = [[0 for _ in range(text2_size + 1)] for _ in range(text1_size + 1)]
        lcs = ""

        for t1_idx in range(1, text1_size + 1):
            for t2_idx in range(1, text2_size + 1):
                print(text1[t1_idx - 1], text2[t2_idx - 1])
                if text1[t1_idx - 1] == text2[t2_idx - 1]:
                    dp[t1_idx][t2_idx] = 1 + dp[t1_idx - 1][t2_idx - 1]
                    lcs += text1[t1_idx - 1]
                else:
                    dp[t1_idx][t2_idx] = max(
                        dp[t1_idx][t2_idx - 1], dp[t1_idx - 1][t2_idx]
                    )
        print(dp, lcs)
        return dp[text1_size][text2_size]


Solution().longestCommonSubsequence("abcde", "ace")

a a
a c
a e
b a
b c
b e
c a
c c
c e
d a
d c
d e
e a
e c
e e
[[0, 0, 0, 0], [0, 1, 1, 1], [0, 1, 1, 1], [0, 1, 2, 2], [0, 1, 2, 2], [0, 1, 2, 3]] ace

3

Longest Common Substring

def longest_common_substring(text1, text2, text1_idx, text2_idx, l):
    if text1_idx < 0 or text2_idx < 0:
        return []
    if text1[text1_idx] == text2[text2_idx]:
        l.append(text1[text1_idx])
        longest_common_substring(text1, text2, text1_idx - 1, text2_idx - 1, l)
        return l
    l = max(
        longest_common_substring(text1, text2, text1_idx - 1, text2_idx, []),
        longest_common_substring(text1, text2, text1_idx, text2_idx - 1, []),
    )
    return l


class Solution:
    def longestCommonSubstring(self, text1: str, text2: str) -> int:

        text1_size = len(text1)
        text2_size = len(text2)

        return longest_common_substring(
            text1, text2, text1_size - 1, text2_size - 1, []
        )[::-1]


Solution().longestCommonSubstring("acd", "lcde")

['c', 'd']

Climb Stairs

def climb_stairs(n, memo):
    if n < 0:
        return 0
    if n == 0:
        return 1
    if n == 1:
        return 1
    if n == 2:
        return 2

    if memo[n] is not None:
        return memo[n]

    memo[n] = climb_stairs(n - 1) + climb_stairs(n - 2)

    return memo[n]


class Solution:
    def climbStairs(self, n: int) -> int:
        memo = [None] * (n + 1)
        return climb_stairs(n, memo)


Solution().climbStairs(2)

2

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

        dp[0] = 1
        dp[1] = 1
        dp[2] = 2

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

        return dp[n]


Solution().climbStairs(2)

2

Longest Increasing Subsequence

from typing import List


def longest_increasing_subseq(nums, size, idx, prev_idx, memo):

    # base case -> increasing idx till the end of the array
    # nothing else to compute
    if idx == size:
        return 0

    if memo[idx][prev_idx + 1] is not None:
        return memo[idx][prev_idx + 1]

    # if i dont take then idx will increase but prev idx will remain same as we have not picked
    no_take = 0 + longest_increasing_subseq(nums, size, idx + 1, prev_idx, memo)

    # if take
    # check condition (are we at the first digit /prev == -1 or the prev value is less than current value)
    take = float("-inf")
    if prev_idx == -1 or nums[prev_idx] < nums[idx]:
        # len = 1 + (idx is incremented and current idx becomes prev idx)
        take = 1 + longest_increasing_subseq(nums, size, idx + 1, idx, memo)

    val = max(no_take, take)
    memo[idx][prev_idx + 1] = val
    return memo[idx][prev_idx + 1]


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        size = len(nums)
        # need to keep memo for both idx and prev idx
        # now that we are starting with -1 memo will be accessed by prev idx + 1
        memo = [[None for _ in range(size + 1)] for _ in range(size)]
        return longest_increasing_subseq(nums, size, 0, -1, memo)


Solution().lengthOfLIS(nums=[10, 9, 2, 5, 3, 7, 101, 18])

4

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        size = len(nums)
        # need to keep memo for both idx and prev idx
        # now that we are starting with -1 memo will be accessed by prev idx + 1
        dp = [[0 for _ in range(size + 1)] for _ in range(size)]

        for idx in range(size - 1, -1, -1):
            for prev_idx in range(idx - 1, -2, -1):

                no_take = 0 + dp[idx][prev_idx + 1]

                take = float("-inf")
                if prev_idx == -1 or nums[prev_idx] < nums[idx]:
                    take = 1 + dp[idx][idx + 1]

                dp[idx][prev_idx + 1] = max(take, no_take)

        print(dp)
        return dp[-1][size - 1]


Solution().lengthOfLIS(nums=[10, 9, 2, 5, 3, 7, 101, 18])

[[1, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 0, 0, 0, 0, 0, 0], [1, 0, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 1, 0, 0, 0, 0, 0], [1, 0, 0, 1, 1, 1, 0, 0, 0], [1, 1, 1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 1, 1, 0, 0]]

0

Coin Change II

def coin_change_ii(coins, index, amount, memo):

    if amount == 0:
        return 1

    if amount < 0:
        return 0

    if (index, amount) in memo:
        return memo[(index, amount)]

    solution = 0
    n_coins = len(coins)
    for i in range(index, n_coins):
        solution = solution + coin_change_ii(coins, i, amount - coins[i], memo)

    memo[(index, amount)] = solution
    return solution


memo = {}
coin_change_ii([2, 2340, 4680], 0, 4681, memo)

0

def coin_change_ii(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for am in range(coin, amount + 1):
            print(am, am - coin, dp)
            dp[am] += dp[am - coin]
    return dp[amount]


coin_change_ii([1, 2, 5], 6)

1 0 [1, 0, 0, 0, 0, 0, 0]
2 1 [1, 1, 0, 0, 0, 0, 0]
3 2 [1, 1, 1, 0, 0, 0, 0]
4 3 [1, 1, 1, 1, 0, 0, 0]
5 4 [1, 1, 1, 1, 1, 0, 0]
6 5 [1, 1, 1, 1, 1, 1, 0]
2 0 [1, 1, 1, 1, 1, 1, 1]
3 1 [1, 1, 2, 1, 1, 1, 1]
4 2 [1, 1, 2, 2, 1, 1, 1]
5 3 [1, 1, 2, 2, 3, 1, 1]
6 4 [1, 1, 2, 2, 3, 3, 1]
5 0 [1, 1, 2, 2, 3, 3, 4]
6 1 [1, 1, 2, 2, 3, 4, 4]

5

Length of longest substring

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        size = len(s)
        if size == 0:
            return 0
        if size == 1:
            return 1

        max_counter = 0

        for slow_idx in range(0, size):
            hashmap = set(s[slow_idx])
            for fast_idx in range(slow_idx + 1, size):
                if s[fast_idx] in hashmap:
                    break
                else:
                    hashmap.add(s[fast_idx])
            max_counter = max(max_counter, len(hashmap))
        return max_counter


Solution().lengthOfLongestSubstring("au")

2

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:

        size = len(s)
        if size == 0:
            return 0
        if size == 1:
            return 1

        hashmap = {}

        slow_idx = 0
        fast_idx = 0
        max_len = 0
        while fast_idx < size:
            if s[fast_idx] not in hashmap:
                hashmap[s[fast_idx]] = fast_idx
            else:
                if hashmap[s[fast_idx]] + 1 > slow_idx:
                    slow_idx = hashmap[s[fast_idx]] + 1
                hashmap[s[fast_idx]] = fast_idx
            max_len = max(fast_idx - slow_idx + 1, max_len)
            fast_idx += 1

        return max_len


Solution().lengthOfLongestSubstring("tmmzuxt")

5

Maximum Subarray

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        size = len(nums)
        max_sum = float("-inf")

        temp_sum = 0

        for idx in range(size):
            temp_sum += nums[idx]
            if temp_sum <= 0:
                temp_sum = 0
            max_sum = max(max_sum, temp_sum)
        return max_sum


Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])

6

Minimum total Triangle

from typing import List


def minimum_total(triangle, size, row_idx, col_idx, memo):

    if row_idx == size - 1:
        return triangle[row_idx][col_idx]

    if memo[row_idx][col_idx] != -1:
        return memo[row_idx][col_idx]

    down = triangle[row_idx][col_idx] + minimum_total(
        triangle, size, row_idx + 1, col_idx, memo
    )
    diagonal = triangle[row_idx][col_idx] + minimum_total(
        triangle, size, row_idx + 1, col_idx + 1, memo
    )
    memo[row_idx][col_idx] = min(down, diagonal)
    return memo[row_idx][col_idx]


class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        size = len(triangle)
        memo = [[-1 for _ in range(size)] for _ in range(size)]
        return minimum_total(triangle, size, 0, 0, memo)


triangle = [[-1], [-2, -3], [-4, -5, -6]]

print(Solution().minimumTotal(triangle))

triangle = [[1], [-2, 3], [-1, 4, -5]]

print(Solution().minimumTotal(triangle))
triangle = [[2], [3, 4], [6, 5, 7], [4, 1, 8, 3]]

print(Solution().minimumTotal(triangle))

-10
-2
11