1155.md

1155. Number of Dice Rolls With Target Sum

Solution 1 (time O(nktarget), space O(n*target))

# Dynamic programming
class Solution(object):
    def numRollsToTarget(self, n, k, target):
        """
        :type n: int
        :type k: int
        :type target: int
        :rtype: int
        """
        dp = [[0] * (target + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        for i in range(1, n + 1):
            for j in range(1, target + 1):
                for k in range(1, k + 1):
                    if j - k >= 0:
                        dp[i][j] = (dp[i][j] + dp[i - 1][j - k]) % (10 ** 9 + 7)
        return dp[n][target]