Problem#
你有 $n$ 個 $k$ 面骰子，點數是 $1$ 到 $k$ ，給你一個目標數字 $t$，問你連續投骰子，最後點數加總起來等於 $t$ 的方法數有多少?
答案可能很大，因此回傳前要模除 $10^9+7$ 。
測資限制#
- $1 \le n, k \le 30$
- $1 \le t \le 1000$
想法#
目標是要骰到點數總和等於 $t$，可以遞迴去搜當前回合($i$)骰到 $j = [1, k]$ 點的狀況下，下回合($i+1$)也可能骰到 $j’ = [1, k]$ 點，如此這樣遞迴去列舉骰到的點數狀況，直到骰完 $n$ 回合(用完所有的骰子)，如果每回合都有紀錄從頭骰到當前回合: $[1, i]$ 骰到的點數總和，如果總和剛好等於 $t$，方法數便加一。
可以用 memorization 來做 top-down dp 的方式加速。
AC Code#
- 時間複雜度: $\mathcal{O}(ntk)$
- 總共有 $n \times t$ 個狀態，每次回合枚舉 $[1, k]$
- 空間複雜度: $\mathcal{O}(nt)$
賞析#
- 看其他人說這題也和換錢問題很像
心得#
一開始完全沒想法，看了 hint 也是，據透題解的圖後，有寫出一個版本但終止條件寫爛了，又再據透一次才對 QQ