Re: [閒聊] 每日LeetCode
※ 引述《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]
--
沒人在乎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.233.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1664701309.A.AAA.html
推
10/02 17:02,
1年前
, 1F
10/02 17:02, 1F
推
10/02 17:03,
1年前
, 2F
10/02 17:03, 2F
→
10/02 17:09,
1年前
, 3F
10/02 17:09, 3F
推
10/02 17:13,
1年前
, 4F
10/02 17:13, 4F
推
10/02 18:08,
1年前
, 5F
10/02 18:08, 5F
討論串 (同標題文章)