• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]LeetCode1155.掷骰子的N种方法|NumberofDiceRollsWithTargetSum

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:山青咏芝(shanqingyongzhi)
➤博客园地址:山青咏芝(www.zengqiang.org
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

You have d dice, and each die has f faces numbered 1, 2, ..., f.

Return the number of possible ways (out of fd total ways) modulo 10^9 + 7 to roll the dice so the sum of the face up numbers equals target.

Example 1:

Input: d = 1, f = 6, target = 3
Output: 1

Example 2:

Input: d = 2, f = 6, target = 7
Output: 6

Example 3:

Input: d = 2, f = 5, target = 10
Output: 1

Example 4:

Input: d = 1, f = 2, target = 3
Output: 0

Example 5:

Input: d = 30, f = 30, target = 500
Output: 222616187 

Constraints:

  • 1 <= d, f <= 30
  • 1 <= target <= 1000

这里有 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

108ms
 1 class Solution {
 2     
 3     var dp = [[Int]]()
 4     
 5     func numRollsToTarget(_ d: Int, _ f: Int, _ target: Int) -> Int {
 6         // var result = 0
 7         // dp = Array(repeating: Array(repeating: -1, count: target + 1), count: d + 1)
 8         // return rollsHelper(d, f, target)
 9         
10         var newDP = Array(repeating: 0, count: target + 1)
11         newDP[0] = 1
12         for i in 0..<d {
13             var newDP1 = Array(repeating: 0, count: target + 1)
14             for j in 1...f {
15                 if j > target {
16                     continue
17                 }
18                 for k in j...target {
19                     newDP1[k] = (newDP1[k] + newDP[k - j]) % 1000000007
20                 }
21             }
22             newDP = newDP1
23         }
24         //print(newDP)
25         return newDP[target]
26     }
27     
28     func rollsHelper(_ d: Int, _ f: Int, _ target: Int) -> Int {
29         
30         if (d == 0 || target <= 0) { 
31             return d == target ? 1 : 0
32         }
33         
34         if dp[d][target] != -1 {
35             return (dp[d][target] - 1)
36         }
37         
38         var result = 0
39         for i in 1...f {
40             result = result + rollsHelper(d - 1, f, target - i) % 1000000007
41         }
42         
43         dp[d][target] = (result + 1) 
44         return result % 1000000007
45     }
46 }

120ms

 1 class Solution {
 2     func numRollsToTarget(_ d: Int, _ f: Int, _ target: Int) -> Int {     
 3         var dp = [[Int]](repeating: [Int](repeating: 0, count: max(target+1, f+1)), count: d)
 4         for i in 0..<f { dp[0][i+1] = 1 }
 5         for i in 1..<d {
 6             for j in 1..<target {               
 7                 for k in 0..<f{ 
 8                     if dp[i-1][j] > 0 {
 9                         let cur = j + k + 1
10                         if cur <= target {
11                             dp[i][cur] = (dp[i][cur] + dp[i-1][j])%(1000_000_007)
12                         }
13                     } else {
14                         break
15                     }
16                 }
17             }
18         }
19         return dp[d-1][target]
20     }
21 }

140ms

 1 class Solution {
 2     func numRollsToTarget(_ d: Int, _ f: Int, _ target: Int) -> Int {     
 3         var len = max(target+1, f+1)
 4         var dp = [[Int]](repeating: [Int](repeating: 0, count: len), count: d)
 5         for i in 0..<f { dp[0][i+1] = 1 }
 6         for i in 1..<d {
 7             for j in 1..<target {               
 8                 for k in 0..<f{ 
 9                     if dp[i-1][j] > 0 {
10                         let cur = j + k + 1
11                         if cur <= target {
12                             dp[i][cur] = (dp[i][cur] + dp[i-1][j])%(1000_000_007)
13                         }
14                     } else {
15                         break
16                     }
17                 }
18             }
19         }
20         return dp[d-1][target]
21     }
22 }

Runtime: 144 ms

Memory Usage: 21.1 MB
 1 class Solution {
 2     func numRollsToTarget(_ d: Int, _ f: Int, _ target: Int) -> Int {
 3         var dp:[Int] = [Int](repeating:0,count:target + 1)
 4         dp[0] = 1
 5         for c in 0..<d
 6         {
 7             for i in stride(from:target,through:0,by:-1)
 8             {
 9                 dp[i] = 0
10                 var x:Int = 1
11                 while(x <= f && x <= i)
12                 {
13                     dp[i] = (dp[i] + dp[i - x]) % 1000000007
14                     x += 1
15                 }
16             }
17         }
18         return dp[target]
19     }
20 }

168ms

 

 1 class Solution {
 2     
 3     var dp = [[Int]]()
 4     
 5     func numRollsToTarget(_ d: Int, _ f: Int, _ target: Int) -> Int {
 6         var result = 0
 7         dp = Array(repeating: Array(repeating: -1, count: target + 1), count: d + 1)
 8         return rollsHelper(d, f, target)
 9     }
10     
11     func rollsHelper(_ d: Int, _ f: Int, _ target: Int) -> Int {
12         
13         if (d == 0 || target <= 0) { 
14             return d == target ? 1 : 0
15         }
16         
17         if dp[d][target] != -1 {
18             return (dp[d][target] - 1)
19         }
20         
21         var result = 0
22         for i in 1...f {
23             result = result + rollsHelper(d - 1, f, target - i) % 1000000007
24         }
25         
26         dp[d][target] = (result + 1) 
27         return result % 1000000007
28     }
29 }

176ms

 1 class Solution {
 2     func numRollsToTarget(_ d: Int, _ f: Int, _ target: Int) -> Int {
 3         var dp = [Int](repeating: 0, count: target + 1)
 4         dp[0] = 1
 5         for i in 1...d {
 6             var dp1 = [Int](repeating: 0, count: target + 1)
 7             for j in 1...f {
 8                 for k in stride(from: max(i, j), through: min(target, i * f), by: 1) {
 9                     dp1[k] = (dp1[k] + dp[k-j]) % 1_000_000_007
10                 }
11             }
12             dp = dp1
13         }
14         return dp[target]
15     }
16 }

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift网络请求(Moya篇)发布时间:2022-07-13
下一篇:
[Swift]LeetCode695.岛屿的最大面积|MaxAreaofIsland发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap