สมมุติว่าเรามีตัวเลข n จำนวนหน้า และมูลค่ารวม เราต้องหาจำนวนวิธีที่จะโยนลูกเต๋า n หน้าให้ได้ทั้งหมด หากคำตอบคือ mod ที่ใหญ่มาก ผลลัพธ์จะเป็น 10**9 + 7.
ดังนั้น หากอินพุตเป็น n =2 หน้า =6 ทั้งหมด =8 ผลลัพธ์จะเป็น 5 เนื่องจากมี 5 วิธีในการสร้าง 8 กับ 2 ลูกเต๋า 6 หน้า (2 และ 6) (6 และ 2) , (3 และ 5), (5 และ 3), (4 และ 4).
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ม :=10^9 + 7
-
dp :=รายการขนาด (รวม + 1) จากนั้นเติม 0
-
สำหรับใบหน้าในระยะ 1 ถึงใบหน้าขั้นต่ำ ให้อัปเดตในแต่ละขั้นรวม +1 ทำ
-
dp[ใบหน้า] :=1
-
-
สำหรับฉันอยู่ในช่วง 0 ถึง n - 2 ทำ
-
สำหรับ j ในช่วงทั้งหมดเป็น 0, ลดลง 1 ทำ
-
dp[j] :=ผลรวมของ dp[j - f] ทั้งหมดสำหรับ f ในช่วง 1 ถึงใบหน้า + 1 เมื่อ j - f>=1
-
-
ส่งคืนองค์ประกอบสุดท้ายของ dp mod m
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution: def solve(self, n, faces, total): m = 10 ** 9 + 7 dp = [0] * (total + 1) for face in range(1, min(faces, total) + 1): dp[face] = 1 for i in range(n - 1): for j in range(total, 0, -1): dp[j] = sum(dp[j - f] for f in range(1, faces + 1) if j - f >= 1) return dp[-1] % m ob = Solution() n = 2 faces = 6 total = 8 print(ob.solve(n, faces, total))
อินพุต
2,6,8
ผลลัพธ์
5
