Re: [閒聊] 每日LeetCode
https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/description
1155. Number of Dice Rolls With Target Sum
給你三個數字 n、k、target，n 表示丟幾次骰子，k 表示骰子有幾面（1~k點），target
表示目標點數，求出丟 n 次骰子後共有幾種可能點數和為 target，因為數字很大所以
要取模運算。
思路：
1.如果骰子全骰到最大的和小於target，不用算可以直接返回 0。
2.定義 f(n, m) 表示使用 n 顆骰子和為 m 的方法數，很明顯的 f(1, 1:k) 都是 1
，而當我們投一顆新骰子時每個點數會產生 k 個新的和，舉例來說當骰子數為2時
可能是 1+1, 1+2, 1+3, ..., 1+k，所以我們遍歷所有之前不為0（可以骰出來的數字）
的點數加上當前的點數做 n 輪之後檢查 f(n, target) 即可。
Java Code：
------------------------------------------------------
class Solution {
private final int MOD = 1000000007;
public int numRollsToTarget(int n, int k, int target) {
if (target > n * k) {
return 0;
}
// 初始化
int[][] dp = new int[n + 1][1001];
for (int i = 1; i <= k; i++) {
dp[1][i] = 1;
}
// 投第幾次
for (int i = 2; i <= n; i++) {
for (int j = 1; j < 1001; j++) {
for (int num = 1; num <= k && num + j <= target; num++) {
dp[i][j + num] = (dp[i][j + num] + dp[i - 1][j]) % MOD;
}
}
}
return dp[n][target];
}
}
------------------------------------------------------
姆咪
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1703608141.A.BCD.html
※ 編輯: Rushia (122.100.73.13 臺灣), 12/27/2023 00:37:19
→
12/27 00:44,
1年前
, 1F
12/27 00:44, 1F
推
12/27 01:01,
1年前
, 2F
12/27 01:01, 2F
推
12/27 01:19,
1年前
, 3F
12/27 01:19, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 584 之 719 篇)：