Leetcode 118: Áp dụng Binomial Coefficients để giải Pascal's Triangle

Pascal's Triangle là một bài giải thuật khá phổ biến. Bạn có thể tham khảo đề, input và output của bài này trên Leetcode:

Loading...

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

LeetCode

Ở khía cạnh giải thuật, đây không phải là một bài quá khó. Nếu bạn nắm các kiến thức căn bản về vòng lặp trong lập trình, bạn hoàn toàn có thể giải bài toán này. Tuy nhiên, Pascal's Triangle có thể được giải rất đơn giản nếu áp dụng kiến thức toán học vào.

Pascal's Triangle

Pascal's Triangle hay tam giác Pascal là một mảng tam giác của các số nhị thức (Binomial Coefficient). Mỗi số trong tam giác Pascal là tổng của hai số trên nó. Input đầu vào của bài toán này là số tầng mà tam giác cần cấu thành và Output sẽ là tam giác hoàn chỉnh với số tầng được cung cấp.

Binomial Coefficients là gì?

Vì mình không phải tìm hiểu quá sâu về toán học nên mình sẽ không giải thích về khái niệm này. Các bạn có thể tham khảo video ở trên để hiểu thêm về Binomial Theorem và Pascal's Triangle. Tuy nhiên, để giải bài giải thuật này, chúng ta sẽ áp dụng công thức của hệ số nhị thức

nCr = n! / r! * (n - r)!

Dịch công thức này dưới dạng code python, ta sẽ có hàm

def calc_binomial_coefficients(n, k):
    return int(math.factorial(n) / (math.factorial(k) * math.factorial(n-k)))

Các cách giải Pascal's Triangle

Naive Approach: Không sử dụng Binomial Coefficient

impl Solution {
 pub fn generate(num_rows: i32) -> Vec<Vec<i32>> {
  let u = num_rows as usize;
  let mut result = Vec::new();
  let mut prev = vec![];
  for i in 0..u {
   if i == 0 {
    result.push(vec![1]);
   } else {
    let mut cur_vec = vec![0; i + 1];
    cur_vec[0] = 1;
    cur_vec[i] = 1;
    for j in 1..i {
     cur_vec[j] = prev[j - 1] + prev[j];
    }
    let cur_prev = cur_vec.to_vec();
    result.push(cur_vec);
    prev = cur_prev;
   }
  }

  result
 }
}

Không quá khó khi bạn chỉ cần hai vòng lặp. Tuy nhiên, giải pháp này sẽ tiêu hao thêm một phần bộ nhớ do việc khởi tạo các mảng tạm thời để lưu trữ dữ liệu. Về ý tưởng của giải pháp trên, với input đầu vào num_rows tương ứng số tầng của tam giác, chúng ta chạy 1 vòng lặp để tạo ra số num_rows tầng. Đỉnh có tam giác (Tầng 0) luôn bằng một. Với mỗi phần tử của các tầng tiếp theo sẽ bằng tổng của hai phần tử phía trên. Do đó ta có dòng này

cur_vec[j] = prev[j - 1] + prev[j];

Sau đó thì ta sẽ thêm mảng tạm thời vào mảng kết quả và trả về mảng kết quả sau khi kết thúc vòng lặp.

Sử dụng Binomial Coefficient

def calc_binomial_coefficient(n, k):
    return int(math.factorial(n) / (math.factorial(k) * math.factorial(n-k)))

def calc_pascal_triangle_bc(level: int):
    result = []
    for l in range(0, level):
        temp = [0] * (l + 1)
        for i in range(0, len(temp)):
            if i == 0 or i == len(temp) - 1:
                temp[i] = 1
                continue
            temp[i] = calc_binomial_coefficient(l, i)
        result.append(temp)
    return result

Tương tự với giải pháp không sử dụng Binomial Coefficient ở trên, với hướng giải quyết này, chúng ta cũng sẽ lặp qua mỗi tầng và mỗi phần tử. Tối đa time complexity chỉ đạt O(n^2) và space complexity sẽ là O(n) cho mảng tạm thời. Áp dụng hàm calc_binomial_coefficient để tính toán tại mỗi phần tử và thêm mảng tạm thời vào mảng tổng khi kết thúc vòng lặp của mạng tạm thời. Trả về mảng tổng và đó chính là kết quả cuối cùng.