1155. Number of Dice Rolls With Target Sum

Loading...LeetCode

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

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

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

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

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)