※ 引述《fxfxxxfxx (爱丽丝)》之铭言：
: 我也要来刷每日一题了
: 今天的题目是 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)
又一个大师== 解法写得很清楚很好懂
倒著更新虽然常看到但还没办法很直觉的想到==
今天就纯贴扣
Python code:
class Solution:
def numRollsToTarget(self, n: int, k: int, target: int) -> int:
dp = [0]*(target+1)
dp[0] = 1
for _ in range(n):
lastk = sum(dp[max(0, target-k):target])%(10**9+7)
for i in range(target, -1, -1):
dp[i] = lastk
lastk = lastk - dp[i-1] + (dp[i-k-1] if i-k > 0 else
0)%(10**9+7)
return dp[target]