# 26.12.2023 [1155. Number of Dice Rolls With Target Sum]
Ways to throw once `n` dices with `k` faces to make `target` sum.
26.12.2023
1155. Number of Dice Rolls With Target Sum medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/451
Problem TLDR
Ways to throw once n
dices with k
faces to make target
sum.
Intuition
Let’s consider each dice and try all the possible face. By repeating the process for all the dice, check if the final sum is equal to the target. The result will only depend on the dice count and target sum, so it can be cached.
Approach
Write brute force DFS, then add HashMap or array cache.
Complexity
Time complexity:
O(nkt), nt - is a DFS search space, k - is the iteration insideSpace complexity:
O(nt)
Code
fun numRollsToTarget(n: Int, k: Int, target: Int): Int {
val dp = mutableMapOf<Pair<Int, Int>, Int>()
fun dfs(c: Int, s: Int): Int =
dp.getOrPut(c to s) { when {
c == 0 -> if (s == 0) 1 else 0
s <= 0 -> 0
else -> (1..k).fold(0) { ways, d ->
(ways + dfs(c - 1, s - d)) % 1_000_000_007
}
} }
return dfs(n, target)
}