Re: [閒聊] 每日LeetCode
我也要來刷每日一題了
今天的題目是 1155. Number of Dice Rolls With Target Sum
給 n 個 k 面骰子(值從 1 到 k)，以及目標target
問總共有多少種骰法總和是target（順序有差，總共有k^n種結果）
並將結果 mod 10^9+7
其中 1 <= n,k <= 30 且 1 <= target <= 1000
第一個直覺的想法會是用 DP 去做，令 DP[i][j] 為 i 個骰子下總和為 j 的總數
則有 DP[i][j] = DP[i-1][j-1] + DP[i-1][j-2] + ... + DP[i-1][j-k]
這樣複雜度會是 O(n*k*target) 感覺有點大
不過既然要加的東西都是連續的，我們可以維護一個陣列 S，並且
定義 S[j] = DP[i][0] + ... + DP[i][j]，則會有
S[j-1] - S[j-k-1] = DP[i-1][j-1] + ... + DP[i-1][j-k]
就不用加 k 次
加上 S 每輪只需要花 O(target) 重算，所以最後的複雜度會是 O(n*target)
空間方面，可以觀察到要更新 DP[i][j] 只會用到 DP[i-1][:j]
所以倒著更新的話可以直接把舊的壓掉，空間會是 O(target)
class Solution {
public:
vector<int> A = vector<int>(1001, 0);
vector<int> S = vector<int>(1001, 1);
const int mod = 1000000007;
int numRollsToTarget(int n, int k, int target) {
A[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = target; j > 0; j--) {
int minus = j-k-1 >= 0 ? S[j-k-1] : 0;
A[j] = (S[j-1] - minus + mod) % mod;
}
A[0] = 0;
S[0] = A[0];
for (int j = 1; j <= target; j++)
S[j] = (S[j-1] + A[j]) % mod;
}
return A[target];
}
};
值得注意的是，雖然複雜度 O(n*target) 樣子長的像多項式時間
但 n 跟 target 以輸入的長度來看只有 log(n) + log(target)
所以實際上這是 pseudo-polynomial，算是非常慢的演算法
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1664672427.A.217.html
推
10/02 09:00,
1年前
, 1F
10/02 09:00, 1F
推
10/02 16:46,
1年前
, 2F
10/02 16:46, 2F
討論串 (同標題文章)