โจทย์
มีลูกเต๋า d ลูก แต่ละลูกมีหน้า f หน้า (เลข 1 ถึง f) หาจำนวนวิธีทอยให้ผลรวมเท่ากับ target modulo 10^9 + 7
ตัวอย่าง: d=2, f=6, target=7 → 6 วิธี (1+6, 2+5, 3+4, 4+3, 5+2, 6+1)
Dynamic Programming (Bottom-up)
dp[i][s] = จำนวนวิธีทอย i ลูกให้ได้ผลรวม s
- Base:
dp[1][face] = 1สำหรับ face = 1..f - Transition:
dp[i][s] = sum(dp[i-1][s-face] for face in 1..f if s-face > 0) - Answer:
dp[d][target] % MOD
การติดตั้ง (Python Implementation)
class Solution:
def numRollsToTarget(self, d: int, f: int, target: int) -> int:
MOD = 10**9 + 7
# dp[i][s] = ways to get sum s with i dice
dp = [[0] * (target + 1) for _ in range(d + 1)]
# Base case: 1 die
for face in range(1, f + 1):
if face <= target:
dp[1][face] = 1
# Fill DP table
for i in range(2, d + 1):
for s in range(i, target + 1): # min sum = i, max = i*f
for face in range(1, f + 1):
if s - face > 0:
dp[i][s] = (dp[i][s] + dp[i-1][s-face]) % MOD
return dp[d][target]
# ทดสอบ
ob = Solution()
print(ob.numRollsToTarget(2, 6, 7)) # 6
print(ob.numRollsToTarget(1, 6, 3)) # 1
print(ob.numRollsToTarget(30, 30, 500)) # Large test
Output
6 1 ... (large number modulo 1e9+7)
Space Optimization: 1D DP
เนื่องจาก dp[i] ขึ้นอยู่กับ dp[i-1] เท่านั้น สามารถลดเหลือ 1 array ได้:
def numRollsToTarget_optimized(self, d: int, f: int, target: int) -> int:
MOD = 10**9 + 7
dp = [0] * (target + 1)
# Base case
for face in range(1, f + 1):
if face <= target:
dp[face] = 1
# Iterate dice
for _ in range(2, d + 1):
new_dp = [0] * (target + 1)
for s in range(1, target + 1):
if dp[s] == 0:
continue
for face in range(1, f + 1):
if s + face <= target:
new_dp[s + face] = (new_dp[s + face] + dp[s]) % MOD
dp = new_dp
return dp[target]
Complexity
- Time: O(d × target × f)
- Space: O(target) (optimized) หรือ O(d × target) (2D)
สรุป
เป็นโจทย์ DP คลาสสิก (Dice Roll / Coin Change variant) จุดสำคัญคือการกำหนด state และ transition ให้ถูกต้อง รวมถึง modulo ในแต่ละขั้นตอนเพื่อป้องกัน overflow
หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ
