夏•◡•センパイ
@davidegg
覺得
Sun, Aug 6, 2023 4:01 AM
1
Coding日記 038
Leetcode_daily
Leetcode_weekly_contest
掰噗~
@baipu
說
Sun, Aug 6, 2023 4:02 AM
沒錯沒錯
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 4:02 AM
https://images.plurk.com/1fBxGH0GjC5yooTpYsuIYB.png

兩題
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 4:02 AM
第三題有想到解法 但是時間不夠debug
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 4:21 AM
daily是什麼鬼畜排列組合問題...看完題目就不想解
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 4:22 AM
Number of Music Playlists - LeetCode
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 4:22 AM
920. Number of Music Playlists
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 4:23 AM
每首歌至少要播一次 ← 沒這個條件都還算簡單...
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 5:51 AM
https://images.plurk.com/2z68ZQQsk2FkhlHUBWDaQO.png

高中排列組合硬幹
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 5:51 AM
還以為會是TLE
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 5:51 AM
感覺這題應該是要用DP
但是我想不到Transition怎麼寫
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 6:00 AM
排列組合的想法：

他如果沒有限制每首歌至少播一次
那問題很簡單
只要關注下一首有幾首歌可以放(沒進CD的歌/CD完的歌)
然後就是單純排列
一路乘下去就是答案

但是這樣寫會把 有歌沒播到的情況也包含進來
那怎麼辦
就用遞迴把這些有歌沒播到的情況扣掉
遞！
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 6:03 AM
比如說 有6首歌
我就算6首歌(以內)的單純排列數-只用5首歌的單純排列-只用四首歌的單純排列...-只用一首歌的單純排列

然後遞迴求出只用N首歌的結果
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 6:08 AM
https://images.plurk.com/6ZPNyNs8RPQENF8tgyCsQg.png
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 6:10 AM
全部n首、恰有i首沒播到的情況
即
C(n,i) 乘上 (剛好播了n-i首 的情況 by 遞迴)
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 6:12 AM
不過這樣寫竟然沒有TLE
時間複雜度應該是O(n*goal)
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 6:12 AM
對欸 這題要DP應該陣列大小也得是(n*goal)
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 6:44 AM
https://images.plurk.com/4THMA3GKnIKChdjrvj6hnQ.png

難怪遞迴效能不差 因為根本沒必要遞迴草
可以直接把簡單排列跟後面的排列組合拆開
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 6:46 AM
只是符號要改一下
因為從「恰用了N首」變成「用了N首以下」
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 6:53 AM
https://images.plurk.com/6eySTRPvGISWrWP3KZ7qsJ.png
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 7:51 AM
https://images.plurk.com/4ThGQOfgiXLf0ueo7PmqOZ.png
想到buttom up DP了
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 7:52 AM
goal = 0的情況想好久
後來才想到什麼歌都不放要當作1
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 7:53 AM
應該說這個只是為了讓g = 1 i = 1的dp填入1
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 7:53 AM
...所以其實從g=1開始也沒問題嘛 草
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 7:53 AM
害我想半天
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 7:59 AM
主要的想法是
DP紀錄用了i首歌的歌單數量
每個步驟把歌單再延長1首歌
那可以放舊歌(放過的歌)
也可以放新歌(沒放過的歌)
放舊歌代表i沒有增加 所以往回找dp[i]
去乘上能放的舊歌 有k首歌還不能放所以剩i-k,最小為0
放新歌代表i比前一個步驟+1 所以往回找dp[i-1]
去乘上能放的新歌 總共有n首歌所以剩n-(i-1)
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 8:20 AM
https://images.plurk.com/fbUXGmTFNuEYHswjaQAet.png

舉個例是這種感覺
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 8:20 AM
我覺得排列組合比較好懂
夏•◡•センパイ
@davidegg
Sun, Aug 6, 2023 8:24 AM
https://images.plurk.com/1X9wZjMwoJt4zTVAWYyQgx.png
一直忘記要mod 1000000007
夏•◡•センパイ
@davidegg
Mon, Aug 7, 2023 4:11 AM
ͨnͦgͩ ͥ日記
夏•◡•センパイ
@davidegg
Mon, Aug 7, 2023 4:12 AM
ͨnͦgͩ_ͥ日記
載入新的回覆