Bài toán Mảng con có tổng lớn nhất

Phân tích bài toán

Đây là một bài toán kinh điển sử dụng Quy hoạch động (Dynamic Programming). Ý tưởng cốt lõi là tìm hiểu xem tại mỗi vị trí trong mảng, liệu ta nên tiếp tục mở rộng mảng con hiện tại hay bắt đầu một mảng con mới.

Xây dựng lời giải

Bước 1: Định nghĩa trạng thái

Gọi dp[i] là tổng lớn nhất của các mảng con kết thúc tại chỉ số i. Với mỗi phần tử, ta có hai lựa chọn:

• Ghép nó vào mảng con trước đó
• Bắt đầu một mảng con mới từ chính nó

Bước 2: Công thức chuyển trạng thái

Tại mỗi vị trí, ta chọn phương án tốt hơn giữa việc nối vào mảng trước đó hoặc bắt đầu mới:

dp[i] = max(nums[i], nums[i] + dp[i-1])

Bước 3: Điều kiện ban đầu

dp[0] = nums[0], vì mảng con duy nhất kết thúc tại vị trí 0 chính là phần tử đầu tiên.

Bước 4: Tối ưu không gian

Vì dp[i] chỉ phụ thuộc vào dp[i-1], ta không cần lưu toàn bộ mảng dp mà chỉ cần một biến lưu giá trị trước đó.

Triển khai mã nguồn

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if not nums:
            return 0
        
        current_sum = nums[0]
        max_sum = nums[0]
        
        for i in range(1, len(nums)):
            # Chọn giữa việc mở rộng mảng hiện tại hoặc bắt đầu mới
            current_sum = max(nums[i], current_sum + nums[i])
            # Cập nhật tổng lớn nhất
            max_sum = max(max_sum, current_sum)
        
        return max_sum

Bài toán Chuỗi con chung dài nhất (Longest Common Subsequence - LCS)

Phân tích bài toán

Bài toán yêu cầu tìm độ dài của chuỗi con chung dài nhất giữa hai chuỗi. Đây cũng là ứng dụng điển hình của Quy hoạch động trên mảng hai chiều.

Xây dựng lời giải

Bước 1: Định nghĩa trạng thái

dp[i][j] biểu diễn độ dài chuỗi con chung dài nhất của tiền tố text1[0:i] và text2[0:j].

Bước 2: Công thức chuyển trạng thái

Xét hai ký tự tại vị trí i-1 và j-1:

• Nếu text1[i-1] == text2[j-1]: Tìm thấy một ký tự chung, cộng thêm 1 vào kết quả của các tiền tố ngắn hơn:

  dp[i][j] = dp[i-1][j-1] + 1

• Nếu text1[i-1] != text2[j-1]: Bỏ qua một ký tự từ một trong hai chuỗi:

  dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Bước 3: Điều kiện ban đầu

Hàng 0 và cột 0 đại diện cho chuỗi rỗng, do đó dp[0][j] = 0 và dp[i][0] = 0 với mọi i, j.

Bước 4: Thứ tự tính toán

Duyệt từ trên xuống dưới, trái sang phải để đảm bảo các trạng thái phụ thuộc đã được tính toán.

Triển khai mã nguồn

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        len1, len2 = len(text1), len(text2)
        
        # Tạo bảng dp với kích thước (len1+1) x (len2+1)
        # Hàng và cột đầu tiên đại diện cho chuỗi rỗng
        lcs_table = [[0] * (len2 + 1) for _ in range(len1 + 1)]
        
        for row in range(1, len1 + 1):
            for col in range(1, len2 + 1):
                if text1[row - 1] == text2[col - 1]:
                    # Ký tự trùng khớp, mở rộng chuỗi con
                    lcs_table[row][col] = lcs_table[row - 1][col - 1] + 1
                else:
                    # Chọn kết quả tốt hơn từ việc bỏ qua một ký tự
                    lcs_table[row][col] = max(
                        lcs_table[row - 1][col], 
                        lcs_table[row][col - 1]
                    )
        
        return lcs_table[len1][len2]