โจทย์
ลูกเต๋ามาตรฐานจะให้ค่าจำนวนเต็มตั้งแต่ 1 ถึง 6 นับจำนวนลำดับผลลัพธ์ที่ไม่ว่างเปล่าและมีลำดับ ซึ่งผลรวมของแต่ละลำดับเท่ากับ target โดยลำดับที่มีลำดับต่างกันถือว่าแตกต่างกัน ให้คืนค่านับลำดับทั้งหมด หารเอาเศษด้วย 1,000,000,007
ให้เขียนฟังก์ชัน dice_combinations(target)
อินพุต
target: ผลรวมที่ต้องการของการทอยทั้งหมด
เอาต์พุต
คืนจำนวนนับของลำดับ หารเอาเศษด้วย 1,000,000,007
เงื่อนไข
1 ≤ target ≤ 1,000,000 การนับแบบหารเอาเศษด้วย 1,000,000,007 หมายถึงให้คืนค่าที่เหลือจากการหารจำนวนนับด้วยเลขนี้
ตัวอย่าง
อินพุต:
target = 2
ผลลัพธ์ที่คาดหวัง:
expected = 2อินพุต:
long long target = 2;
ผลลัพธ์ที่คาดหวัง:
long long expected = 2;อินพุต:
long target = 2;
ผลลัพธ์ที่คาดหวัง:
long expected = 2;คำอธิบาย
มี 2 ลำดับ คือ [2] และ [1, 1]
อินพุต:
target = 4
ผลลัพธ์ที่คาดหวัง:
expected = 8อินพุต:
long long target = 4;
ผลลัพธ์ที่คาดหวัง:
long long expected = 8;อินพุต:
long target = 4;
ผลลัพธ์ที่คาดหวัง:
long expected = 8;คำอธิบาย
ลำดับที่เป็นไปได้คือ [4], [1,3], [3,1], [2,2], [1,1,2], [1,2,1], [2,1,1], และ [1,1,1,1]
แนวทางการแก้
ลองทำเองก่อน แล้วค่อยเปิดคำใบ้ทีละข้อ
คำใบ้ 1
มองผลรวมเล็ก ๆ เป็นตัวต่อสำหรับเป้าหมาย
คำใบ้ 2
ใช้ค่าที่นับสะสมสำหรับแต่ละผลรวม โดยอิงจาก 6 ผลรวมก่อนหน้า
คำใบ้ 3
อย่าลืมใช้ modulo ทุกครั้งที่บวก และจัดการผลรวมที่ต่ำกว่า 1 แยกต่างหาก
ความซับซ้อนที่คาดหวัง
เวลา O(target), หน่วยความจำเพิ่ม O(target)
แหล่งอ้างอิง
โจทย์นี้ปรับให้เหมาะกับ CodeUtility กรุณาทำตามคำชี้แจงและข้อจำกัดด้านบน