Giải bài toán Pascal's Triangle (LeetCode 118) - Hướng dẫn cho người mới bắt đầu

Bài toán Pascal's Triangle trên LeetCode 118 là một trong những đề tài kinh điển và rất thích hợp cho người mới học lập trình thuật toán. Dù nghe có vẻ toán học, nhưng thực ra đây là một bài tập tuyệt vời để làm quen với kỹ năng thao tác mảng và nhận dạng quy luật. Bài viết này sẽ dẫn dắt bạn từng bước xây dựng tam giác Pascal cùng cách cài đặt bằng C++ một cách trực quan.

Bài toán: Xây dựng tam giác Pascal

Yêu cầu của đề bài là tạo ra numRows hàng đầu tiên của tam giác Pascal.

Tam giác Pascal là gì?

• Mỗi hàng là một dãy số tam giác.
• Phần tử đầu và cuối của mỗi hàng luôn bằng 1.
• Các phần tử giữa là tổng của hai số ngay phía trên nó của hàng trước.

Ví dụ với numRows = 5, ta có tam giác như sau:

[
 [1],         // Hàng 0
 [1, 1],      // Hàng 1
 [1, 2, 1],   // Hàng 2
 [1, 3, 3, 1],// Hàng 3
 [1, 4, 6, 4, 1] // Hàng 4
]

Như bạn thấy, số 2 ở hàng 2 là tổng 1 + 1 ở hàng 1. Số 3 ở hàng 3 là tổng 1 + 2 hoặc 2 + 1 ở hàng 2, đúng theo quy luật của tam giác.

Ràng buộc quan trọng: 1 <= numRows <= 30, giúp ta yên tâm xây dựng giải pháp không cần tối ưu cực đại.

Ý tưởng và cách xây dựng tam giác

Trước khi lập trình, hãy nhìn cách xây tam giác từng hàng bằng tay:

• Hàng 0: luôn là [1]
• Hàng 1: luôn là [1, 1]
• Hàng 2: bắt đầu và kết thúc bằng 1, phần tử giữa là tổng 1 + 1 = 2 → [1, 2, 1]
• Hàng 3: bắt đầu và kết thúc bằng 1
  • Phần tử thứ 2: 1 + 2 = 3
  • Phần tử thứ 3: 2 + 1 = 3 → [1, 3, 3, 1]

Mỗi hàng hoàn toàn phụ thuộc vào hàng ngay trước đó. Đây là một dạng bài toán điển hình của lập trình động (Dynamic Programming): kết quả cho hàng hiện tại được tính dựa trên kết quả đã giải được của hàng trước.

Cách tiếp cận chi tiết

Bước thực hiện như sau:

1. Khởi tạo một danh sách ans để chứa toàn bộ tam giác dưới dạng vector<vector<int>>.

2. Duyệt qua từng hàng từ 0 đến numRows - 1 (đặt biến vòng lặp là i).

3. Với mỗi hàng i:

   • Tạo một vector tạm temp có kích thước i + 1, khởi tạo tất cả phần tử trong đó là 1 (đảm bảo phần tử đầu và cuối là 1).
   • Nếu i >= 2, tính các phần tử ở vị trí từ 1 đến i-1 theo công thức:
     temp[j] = ans[i-1][j-1] + ans[i-1][j]

4. Thêm hàng temp vừa tạo vào ans.

5. Sau cùng trả về ans chứa toàn bộ tam giác Pascal.

Mã nguồn ví dụ bằng C++

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans; // Lưu tam giác Pascal

        // Duyệt từng hàng từ 0 đến numRows - 1
        for (int i = 0; i < numRows; ++i) {
            vector<int> temp(i + 1, 1); // Khởi tạo hàng mới với tất cả phần tử là 1

            // Tính các phần tử trong (nếu i >= 2)
            if (i >= 2) {
                for (int j = 1; j < i; ++j) {
                    temp[j] = ans[i-1][j-1] + ans[i-1][j]; // Tổng 2 phần tử trên hàng trên
                }
            }
            ans.push_back(temp); // Thêm hàng vào kết quả
        }
        return ans;
    }
};

Phân tích độ phức tạp

• Thời gian: O(numRows^2), vì vòng lặp ngoài chạy numRows lần, vòng trong chạy tối đa numRows lần, tổng cộng tỉ lệ với bình phương numRows.

• Bộ nhớ: O(numRows^2), lưu tam giác có số phần tử bằng tổng 1 + 2 + ... + numRows.

Kết luận

• Nhận dạng mẫu & quy luật là chìa khóa: Bài toán được giải đơn giản nhờ phát hiện ra mối liên hệ giữa các hàng.

• Lập trình động rất hữu dụng: Xử lý bài toán xây dựng từng bước dựa trên kết quả trước.

• Sử dụng thao tác mảng: Là bài tập cơ bản giúp bạn nhanh chóng làm quen với cấu trúc dữ liệu phức tạp.

• Chú ý các trường hợp đặc biệt: Hàng đầu tiên và hàng thứ hai dễ xử lý vì phần tử toàn 1.

Chúc bạn có những giờ phút học tập vui vẻ và tiếp tục khám phá những bài toán thú vị hơn trong lập trình! Hãy kiên nhẫn luyện tập, những bài toán khó chỉ là thử thách để bạn vươn lên mà thôi.