{"id":5421,"date":"2019-08-11T12:43:49","date_gmt":"2019-08-11T19:43:49","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5421"},"modified":"2019-08-11T21:30:14","modified_gmt":"2019-08-12T04:30:14","slug":"leetcode-1155-number-of-dice-rolls-with-target-sum","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1155-number-of-dice-rolls-with-target-sum\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1155. Number of Dice Rolls With Target Sum"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1155. Number of Dice Rolls With Target Sum - \u5237\u9898\u627e\u5de5\u4f5c EP263\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/J9s7402s5FA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>You have&nbsp;<code>d<\/code>&nbsp;dice, and each die has&nbsp;<code>f<\/code>&nbsp;faces numbered&nbsp;<code>1, 2, ..., f<\/code>.<\/p>\n\n\n\n<p>Return the number of possible ways (out of&nbsp;<code>f<sup>d<\/sup><\/code>&nbsp;total ways)&nbsp;<strong>modulo&nbsp;<code>10^9 + 7<\/code><\/strong>&nbsp;to roll the dice so the sum of the face up numbers equals&nbsp;<code>target<\/code>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> d = 1, f = 6, target = 3\n<strong>Output:<\/strong> 1\n<strong>Explanation: <\/strong>\nYou throw one die with 6 faces.  There is only one way to get a sum of 3.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> d = 2, f = 6, target = 7\n<strong>Output:<\/strong> 6\n<strong>Explanation: <\/strong>\nYou throw two dice, each with 6 faces.  There are 6 ways to get a sum of 7:\n1+6, 2+5, 3+4, 4+3, 5+2, 6+1.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> d = 2, f = 5, target = 10\n<strong>Output:<\/strong> 1\n<strong>Explanation: <\/strong>\nYou throw two dice, each with 5 faces.  There is only one way to get a sum of 10: 5+5.\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> d = 1, f = 2, target = 3\n<strong>Output:<\/strong> 0\n<strong>Explanation: <\/strong>\nYou throw one die with 2 faces.  There is no way to get a sum of 3.\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> d = 30, f = 30, target = 500\n<strong>Output:<\/strong> 222616187\n<strong>Explanation: <\/strong>\nThe answer must be returned modulo 10^9 + 7.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= d, f &lt;= 30<\/code><\/li><li><code>1 &lt;= target &lt;= 1000<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: DP<\/strong><\/h2>\n\n\n\n<p>definition: dp[i][k] := ways to have sum of k using all first i dices.<br>Init: dp[0][0] = 1<br>transition: dp[i][k] = sum(dp[i &#8211; 1][k &#8211; j]),  1 &lt;= j  &lt;= f<br>ans: dp[d][target]<\/p>\n\n\n\n<p>Time complexity: O(|d|*|f|*target)<br>Space complexity: O(|d|*target) -&gt; O(target)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua, 32ms, 10.8MB\nclass Solution {\npublic:\n  int numRollsToTarget(int d, int f, int target) {\n    constexpr int kMod = 1e9 + 7;\n    vector<vector<int>> dp(d + 1, vector<int>(target + 1));\n    dp[0][0] = 1;\n    for (int i = 1; i <= d; ++i)\n      for (int j = 1; j <= f; ++j)\n        for (int k = j; k <= target; ++k)\n          dp[i][k] = (dp[i][k] + dp[i - 1][k - j]) % kMod;\n    return dp[d][target];\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">O(target)<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua, 40 ms, 8.8MB\nclass Solution {\npublic:\n  int numRollsToTarget(int d, int f, int target) {\n    constexpr int kMod = 1e9 + 7;\n    vector<int> dp(target + 1);\n    dp[0] = 1;\n    for (int i = 1; i <= d; ++i) \n      for (int k = target; k >= 0; --k) {\n        dp[k] = 0;\n        for (int j = 1; j <= f &#038;&#038; j <= k; ++j)        \n          dp[k] = (dp[k] + dp[k - j]) % kMod;\n      }\n    \n    return dp[target];\n  }\n};\n<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">\n# Author: Huahua\nfrom functools import lru_cache\nclass Solution:\n  def numRollsToTarget(self, d: int, f: int, target: int) -> int:\n    mod = 10 ** 9 + 7    \n    # Number of ways to have target t using i dices.\n    @lru_cache(maxsize=None)\n    def dp(i, t):\n      if i == 0: return 1 if t == 0 else 0\n      # Pruning 388 ms -> 132 ms\n      if t > f * i or t < i: return 0\n      ans = 0\n      for k in range(1, f + 1):\n        ans = (ans + dp(i - 1, t - k)) % mod\n      return ans    \n    return dp(d, target)\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You have&nbsp;d&nbsp;dice, and each die has&nbsp;f&nbsp;faces numbered&nbsp;1, 2, &#8230;, f. Return the number of possible ways (out of&nbsp;fd&nbsp;total ways)&nbsp;modulo&nbsp;10^9 + 7&nbsp;to roll the dice so&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[18,177],"class_list":["post-5421","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-dp","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5421","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5421"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5421\/revisions"}],"predecessor-version":[{"id":5434,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5421\/revisions\/5434"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5421"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5421"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5421"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}