Cách tạo tam giác Pascal cho số cho trước trong C#

Tam giác Pascal là mẫu số hình tam giác, ứng dụng nhiều trong toán học và thống kê, giúp tính tổ hợp. Mỗi số là tổng hai số ngay trên nó. Số đầu và cuối mỗi hàng luôn là 1.

Độ phức tạp thời gian: O(N²)

Độ phức tạp không gian: O(N²)

Ví dụ

public class Arrays
{
    public List<List<int>> GeneratePascal(int n)
    {
        List<List<int>> res = new List<List<int>>();
        if (n <= 0)
        {
            return null;
        }
        List<int> first = new List<int> { 1 };
        res.Add(first);
        if (n == 1)
        {
            return res;
        }
        for (int i = 2; i <= n; i++)
        {
            List<int> prev = res.Last();
            List<int> cur = new List<int>();
            for (int temp = 0; temp < i; temp++)
            {
                cur.Add(1);
            }
            for (int j = 1; j < i - 1; j++)
            {
                cur[j] = prev[j - 1] + prev[j];
            }
            res.Add(cur);
        }
        return res;
    }
}

static void Main(string[] args)
{
    Arrays s = new Arrays();
    var res = s.GeneratePascal(5);
    // Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
}

Kết quả đầu ra

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

Lưu ý: Code gốc vòng lặp i < n chỉ tạo n-1 hàng. Đã sửa thành i <= n để tạo đúng n hàng.