Có Video Toán và thuật toán mỗi ngày

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1) # row
        n = len(word2) # col
        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(n + 1):
            dp[0][i] = i
        for i in range(m + 1):
            dp[i][0] = i
        for i in range(m):
            for j in range(n):
                id = i + 1
                jd = j + 1
                if word1[i] != word2[j]:
                    dp[id][jd] = min(dp[id-1][jd-1], dp[id][jd - 1], dp[id - 1][jd]) + 1
                else:
                    dp[id][jd] = dp[id - 1][jd - 1]
        return dp[m][n]

class Solution:
    def numDecodings(self, s: str) -> int:
        if len(s) == 1:
            if s[0] == "0":
                return 0
            return 1
        dp = [0 for _ in range(len(s) + 1)]
        dp[0] = 1
        for i in range(len(s)):
            id = i + 1
            if s[i] != "0":
                dp[id] = dp[id - 1]
            if i > 0:
                twoDigit = int(s[i-1] + s[i])
                if 10 <= twoDigit <= 26:
                    dp[id] += dp[id-2]
        return dp[len(s)]

func numTrees(n int) int {
    memo := make(map[int]int)
    return countTree(n, memo)
}

func countTree(n int, memo map[int]int) int {
    if n == 0 || n == 1 {
        return 1
    }
    count := 0
    for i := 1; i <= n; i++ {
        if _, exists := memo[i-1]; !exists {
            memo[i-1] = countTree(i-1, memo)
        }
        if _, exists := memo[n-i]; !exists {
            memo[n-i] = countTree(n-i, memo)
        }
        count += memo[i-1] * memo[n-i]
    }
    return count
}

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0 for _ in range(n + 1)]
        dp[0], dp[1] = 1, 1
        for i in range(2, n + 1):
            for j in range(1, i + 1):
                dp[i] += dp[j-1] * dp[i - j]
        return dp[n]

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        row, col = len(matrix), len(matrix[0])
        height = [0] * col
        left = [0] * col
        right = [col] * col # điểm phải xa nhất mặc định là = len of col
        max_area = 0
        for i in range(row):
            currentLeft, currentRight = 0, col
            for j in range(col):
                if matrix[i][j] == '1':
                    height[j] += 1
                else:
                    height[j] = 0
            for j in range(col):
                if matrix[i][j] == '1':
                    left[j] = max(left[j], currentLeft) # tracking điểm 0
                else:
                    left[j] = 0
                    currentLeft = j + 1 # skip current left
            for j in range(col - 1, -1, -1): # -1 including index 0
                if matrix[i][j] == '1':
                    right[j] = min(right[j], currentRight) # righ gan nhat
                else:
                    right[j] = col # reset right
                    currentRight = j # col = 5, j = 4, ko cần j - 1
            for j in range(col):
                max_area = max(max_area, (right[j] - left[j])*height[j])
        return max_area