# 1155. Number of Dice Rolls With Target Sum

{% embed url="<https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/>" %}

很容易猜到是`DP`，不过是`(d, target)`二维的，`f`一直不变。

结束边界`d==0`的时候其实有两个情况，一是正好达到target，那就是刚好1种掷法，如果target没达到，就不存在掷法。

状态转换是个`sum`方程，即掷d个骰子凑target的方法，等于掷`(d-1)`个凑`target-k` (k是1到f的任意数）方法之和。

一维DP比较容易 bottom-up 写，多维就是 top-down 写起来比较容易了。

```python
class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:
        dp = dict()
        def roll(n, target):
            if (n, target) in dp:
                return dp[(n, target)]
            elif n == 0:
                if target > 0: return 0
                else: return 1
            dp[(n, target)] = sum([roll(n-1, x) for x in range(max(0, target-f), target)])
            return dp[(n, target)]
        return roll(d, target)%(10**9+7)
```
