a0928391091
(羊貓貓==大大↑新手↓==把寫過的東西丟丟看)
學校
:
國立嘉義高級中學
編號 : 40778
來源 : [1.164.164.219]
最後登入時間 ：
2023-08-15 11:12:28
dp[i] = dp[i-1]*(i-1) + dp[i-2]*(i-2)
dp[0] = 0
dp[1] = 1
有證明嗎?
一般可以找到上述的解答但詳細知道遞迴規律的人應該都略懂略懂
放入第N個工作時
會是N-1的種類*N-1
因為有N-1可以插入
接來比較不同的是
假使他放入每一個工作後面時 就會有一個新的工作排程
除了放入N-1編號的後面
這樣只有N-2個放置可以插入
但是放入的種類會是(N-2)的種類*(N-2)
上述找到的註解個人看的不是很懂...所以我自己重新推敲之後可以解釋於下面：
(1)當前面 N-1個排程已經排列好這時要插入 Nth排程, 可以選擇的位置是 N-1個(不能放在N-1的號碼後面)
(2)前面的 N-2個合法排程中(N-1)th黏在(N-2)th後面，原本是非法的但這時 Nth排程放入這兩個號碼當中就變合法，(N-2)th 可以出現的位置有 N-2種可能
(2)的條件在(1)的情況時是非法所以互不干擾但計算 Nth時就直接疊加
因為現在只有一個 Nth排程可以選擇插入的位置，所以不用考慮 連續3個黏在一起的情況
dp[i] = dp[i-1]*(i-1) + dp[i-2]*(i-2)
dp[0] = 0
dp[1] = 1
有證明嗎?
一般可以找到上述的解答但詳細知道遞迴規律的人應該都略懂略懂
放入第N個工作時
會是N-1的種類*N-1
因為有N-1可以插入
接來比較不同的是
假使他放入每一個工作後面時 就會有一個新的工作排程
除了放入N-1編號的後面
這樣只有N-2個放置可以插入
但是放入的種類會是(N-2)的種類*(N-2)
上述找到的註解個人看的不是很懂...所以我自己重新推敲之後可以解釋於下面：
(1)當前面 N-1個排程已經排列好這時要插入 Nth排程, 可以選擇的位置是 N-1個(不能放在N-1的號碼後面)
(2)前面的 N-2個合法排程中(N-1)th黏在(N-2)th後面，原本是非法的但這時 Nth排程放入這兩個號碼當中就變合法，(N-2)th 可以出現的位置有 N-2種可能
(2)的條件在(1)的情況時是非法所以互不干擾但計算 Nth時就直接疊加
因為現在只有一個 Nth排程可以選擇插入的位置，所以不用考慮 連續3個黏在一起的情況
(2)前面的 N-2個合法排程中(N-1)th黏在(N-2)th後面，原本是非法的但這時 Nth排程放入這兩個號碼當中就變合法，(N-2)th 可以出現的位置有 N-2種可能
^^^
這個情況應該改為 連號的非法情況有(1,2)(2,3)...(N-2,N-1) 這N-2種可能性才對，這時 Nth插入上述的連續對中就變合法