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

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [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 }