这里有 d 个一样的骰子，每个骰子上都有 f 个面，分别标号为 1, 2, …, f。
我们约定：掷骰子的得到总点数为各骰子面朝上的数字的总和。
如果需要掷出的总点数为 target，请你计算出有多少种不同的组合情况（所有的组合情况总共有 f^d 种），模 10^9 + 7 后返回。
示例 1：
输入：d = 1, f = 6, target = 3
输出：1
示例 2：
输入：d = 2, f = 6, target = 7
输出：6
示例 3：
输入：d = 2, f = 5, target = 10
输出：1
示例 4：
输入：d = 1, f = 2, target = 3
输出：0
示例 5：
输入：d = 30, f = 30, target = 500
输出：222616187
提示：
1 <= d, f <= 30
1 <= target <= 1000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-dice-rolls-with-target-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
十位数级别的数据规模，暗示回溯。
题目问的是有多少种不同的组合，明示回溯。
所以本题用回溯解题：
因为数据规模有点大，所以要用记忆化搜索的方法，把每个子问题的解记录下来，
方便下一次处理相同的子问题的时候可以直接读取结果，而不用往下搜索。
class Solution(object):
def numRollsToTarget(self, d, f, target):
"""
:type d: int
:type f: int
:type target: int
:rtype: int
"""
record = dict()
def backtrack(dice, face, t):
if (dice, face, t) in record: #如果已经知道当前问题的解
return record[(dice, face, t)] #直接读取即可
if dice == 0: #当没有骰子的时候，判断一下是不是刚好找到target
return 1 if t == 0 else 0
if t < 0 or dice <= 0: #无效的时候没有解，所以返回0
return 0
tmp = 0 #tmp用于记录当前问题有多少个解
for i in range(1, face + 1): #尝试所有的组合
tmp += backtrack(dice - 1, face, t - i)
record[(dice, face, t)] = tmp #把解存起来，方便以后用
return tmp
backtrack(d, f, target)
return max(record.values()) % (10 ** 9 + 7) #最大的解就是母问题的解