1155. 목표 합계가 있는 주사위 굴림 수
4736 단어 algorithmscpp
설명
n
개의 주사위가 있고 각 주사위에는 k
에서 1
까지 번호가 매겨진 k
개의 면이 있습니다.
n
, k
및 target
세 개의 정수가 주어지면 앞면 숫자의 합이 kn
가 되도록 주사위를 굴릴 수 있는 가능한 방법의 수를 반환합니다. 답변이 너무 클 수 있으므로 모듈로 반환합니다target
.
예 1:
Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.
예 2:
Input: n = 2, k = 6, target = 7
Output: 6
Explanation: You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.
예 3:
Input: n = 30, k = 30, target = 500
Output: 222616187
Explanation: The answer must be returned modulo 109 + 7.
제약:
Input: n = 1, k = 6, target = 3
Output: 1
Explanation: You throw one die with 6 faces.
There is only one way to get a sum of 3.
Input: n = 2, k = 6, target = 7
Output: 6
Explanation: You throw two dice, each with 6 faces.
There are 6 ways to get a sum of 7: 1+6, 2+5, 3+4, 4+3, 5+2, 6+1.
Input: n = 30, k = 30, target = 500
Output: 222616187
Explanation: The answer must be returned modulo 109 + 7.
109 + 7
1 <= n, k <= 30
솔루션
class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
const int MOD = 1e9 + 7;
vector<int> f(target + 1, 0);
f[0] = 1;
for (int i = 1; i <= n; i++) {// 枚举所有物品
for (int j = target; j >= 0; j--) { // 枚举体积, 从大到小
f[j] = 0;
for (int u = 1; u <= k & u <= j; u++) {
f[j] = (f[j] + f[j - u]) % MOD;
}
}
}
return f[target];
}
};
Reference
이 문제에 관하여(1155. 목표 합계가 있는 주사위 굴림 수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://dev.to/jiangwenqi/1155-number-of-dice-rolls-with-target-sum-m5h
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
class Solution {
public:
int numRollsToTarget(int n, int k, int target) {
const int MOD = 1e9 + 7;
vector<int> f(target + 1, 0);
f[0] = 1;
for (int i = 1; i <= n; i++) {// 枚举所有物品
for (int j = target; j >= 0; j--) { // 枚举体积, 从大到小
f[j] = 0;
for (int u = 1; u <= k & u <= j; u++) {
f[j] = (f[j] + f[j - u]) % MOD;
}
}
}
return f[target];
}
};
Reference
이 문제에 관하여(1155. 목표 합계가 있는 주사위 굴림 수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/jiangwenqi/1155-number-of-dice-rolls-with-target-sum-m5h텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)