LeetCode 1155: Number of Dice Rolls With Target Sum ·

基本資料
#

難易度: medium 第一次嘗試：2026-08-23 來源：Day 44 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

LC 1155: pass after state and base-case repair
explain why LC 1155 needs per-die layers and newDp
say one clean difference between LC 494, LC 518, and LC 1155

當天筆記摘錄
#

Problem 2 - LC 1155 Number of Dice Rolls With Target Sum
#

Pattern: layered counting DP with bounded per-step choices.

Why This Fits
#

This is not subset choice and not unbounded reuse.

The real question is:

after rolling exactly d dice, how many ways produce sum s?

Core State / Invariant
#

2D form:

dp[d][s] = number of ways to make sum s using exactly d dice

Compressed form:

dp[s] = number of ways from the previous dice layer
newDp[s] = number of ways for the current dice layer

Base Case
#

Before rolling any dice:

dp[0] = 1

Reason:

there is exactly one way to make sum 0 with 0 dice

Transition
#

For each die, for each target sum, try every face:

newDp[s] += dp[s - face]

when:

s - face >= 0

Apply modulo after each addition.

Why `newDp` Is Required
#

The current layer must only read:

states from d - 1 dice

If updated in place, one die could contribute multiple times in the same layer, which is incorrect.

Complexity
#

Time: O(n * target * k)
Space: O(target)

Common Mistakes
#

wrong base-case explanation for dp[0]
trying to reuse a single array in place like LC 518
saying this is unbounded knapsack
forgetting modulo in the recurrence

Strong Spoken Explanation
#

I model this as counting ways by dice layer. dp[s] means the number of ways to make sum s from the previous number of dice, and for each new die I build a fresh newDp. For each target sum and each face value from 1 to k, I add the number of ways to reach s - face from the previous layer. The key invariant is that when computing the layer for d dice, I must only read states from d - 1 dice, which is why I use newDp instead of in-place updates.

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

class Solution:
    def numRollsToTarget(self, n: int, k: int, target: int) -> int:
        mod = 10 ** 9 + 7
        dp = [0] * (target + 1)
        dp[0] = 1

        for _ in range(n):
            ndp = [0] * (target + 1)
            for s in range(target + 1):
                if dp[s] == 0:
                    continue
                for face in range(1, k + 1):
                    if s + face <= target:
                        ndp[s + face] = (ndp[s + face] + dp[s]) % mod
            dp = ndp

        return dp[target]