leetcode

commit bf835215db3c2b630e325b4957b34761deab7d9a
parent 048e32ebbf9cfca391f060f5b5582b40f226f336
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 26 Dec 2023 17:39:51 +0000

Daily Problem

Diffstat:
A
Problems/1155.cpp
 | 
19
+++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 20 insertions(+), 0 deletions(-)
diff --git a/Problems/1155.cpp b/Problems/1155.cpp
@@ -0,0 +1,19 @@
+class Solution {
+    static const int MOD = 1E9 + 7;
+    static int dp[31][1001];
+
+  public:
+    Solution() { memset(dp, 0xFF, sizeof(dp)); }
+    int numRollsToTarget(int n, int k, int target, int crnt = 0) {
+        if (target < 0) return 0;
+        if (crnt == n) return target == 0;
+        if (dp[crnt][target] != -1) return dp[crnt][target];
+        int res = 0;
+        for (int i = 1; i <= k; i++) {
+            res = (res + numRollsToTarget(n, k, target - i, crnt + 1)) % MOD;
+        }
+        return dp[crnt][target] = res;
+    }
+};
+
+int Solution::dp[31][1001];
diff --git a/README.md b/README.md
@@ -597,6 +597,7 @@ for solving problems.
 |  1143  |   Medium   | [Longest Common Subsequence](Problems/1143.cpp)                                                    |
 |  1146  |   Medium   | [Snapshot Array](Problems/1146.cpp)                                                                |
 |  1148  |    Easy    | [Article Views I](Problems/1148.cpp)                                                               |
+|  1155  |   Medium   | [Number of Dice Rolls With Target Sum](Problems/1155.cpp)                                          |
 |  1158  |   Medium   | [Market Analysis I](Problems/1158.cpp)                                                             |
 |  1160  |    Easy    | [Find Words That Can Be Formed by Characters](Problems/1160.cpp)                                   |
 |  1161  |   Medium   | [Maximum Level Sum of a Binary Tree](Problems/1161.cpp)                                            |