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