สมมติว่าเราต้องคำนวณค่า nCr หลายครั้ง เราสามารถแก้ปัญหานี้ได้อย่างมีประสิทธิภาพ หากเราเก็บค่า nCr ที่ต่ำกว่า เราจะสามารถหาค่าที่สูงกว่าได้อย่างง่ายดาย ถ้าเรามี n เราก็ต้องหารายการของ nC0 ถึง nCn หากคำตอบมีขนาดใหญ่เกินไป ให้ส่งคืนโมดูลนั้น 10^9
ดังนั้น หากอินพุตเป็น n =6 เอาต์พุตจะเป็น [1, 6, 15, 20, 15, 6, 1]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- items :=รายการที่มีองค์ประกอบเดียว 1
- สำหรับ r ในช่วง 1 ถึง n ทำ
- แทรกพื้นของ (องค์ประกอบสุดท้ายของรายการ * (n-r+1) /r) ที่ส่วนท้ายของรายการ
- items[n-2] :=items[n-2] mod 10^9 โดยที่ 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))
อินพุต
6
ผลลัพธ์
[1, 6, 15, 20, 15, 6, 1]
