我也要來刷每日一題了
今天的題目是 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