Giả sử chúng ta phải tính giá trị nCr nhiều lần. Chúng tôi có thể giải quyết vấn đề này theo cách rất hiệu quả. Nếu chúng ta lưu trữ các giá trị thấp hơn của nCr, chúng ta có thể dễ dàng tìm thấy các giá trị cao hơn. Vì vậy, nếu chúng ta có n, chúng ta phải tìm danh sách từ nC0 đến nCn. Nếu câu trả lời quá lớn thì hãy trả về modulo đó 10 ^ 9.
Vì vậy, nếu đầu vào là n =6, thì đầu ra sẽ là [1, 6, 15, 20, 15, 6, 1].
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- items:=một danh sách có 1 phần tử duy nhất
- đối với r trong phạm vi từ 1 đến n, thực hiện
- chèn tầng của (phần tử cuối cùng của các mục * (n-r + 1) / r) vào cuối các mục
- items [n-2]:=items [n-2] mod 10 ^ 9 trong đó n là kích thước của các mặt hàng
- trả lại các mặt hàng
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
def solve(n): items = [1] for r in range(1,n+1): items.append(items[-1]*(n-r+1)//r) items[-2] %= 10**9 return items n = 6 print(solve(n))
Đầu vào
6
Đầu ra
[1, 6, 15, 20, 15, 6, 1]