#39441: dp式
zhoudaniel02@gmail.com
(周孝倫)
學校
:
銘傳大學
編號 : 235507
來源 : [114.136.241.153]
最後登入時間 ：
2025-06-30 10:24:51
整個人的數量是序列的長度，為n
傳球的次數為m
dp[m][k]表示傳球第m次，最終落在k號手上的樣本數
由於第m次傳回0，第m-1次就必須傳到1或n-1(上一次傳到0的左右兩邊)
因此dp[m][k]=dp[m-1][(k-1+n)%n]+dp[m-1][(k+1)%n]
且傳0次球，如果不是從0開始傳，就不可能回到0
因此dp[0][0]=1，其餘的dp[0][k]=0
#39442: Re: dp式
zhoudaniel02@gmail.com
(周孝倫)
學校
:
銘傳大學
編號 : 235507
來源 : [114.136.241.153]
最後登入時間 ：
2025-06-30 10:24:51
整個人的數量是序列的長度，為n
傳球的次數為m
dp[m][k]表示傳球第m次，最終落在k號手上的樣本數
由於第m次傳回0，第m-1次就必須傳到1或n-1(上一次傳到0的左右兩邊)
因此dp[m][k]=dp[m-1][(k-1+n)%n]+dp[m-1][(k+1)%n]
且傳0次球，如果不是從0開始傳，就不可能回到0
因此dp[0][0]=1，其餘的dp[0][k]=0
對了 時間複雜度是O(n*m)