題 意: 給定兩個整數 k, n，如果一個由 0 ~ k 組成長度為 n 的字串是 "tight"，則代表相鄰的兩位數差不超過 1，問所有字串中包含 "tight" 字串的比例。
解法: 用DP解，當求第 i 層的答案時，會跟第 i-1 層的答案相關。
dp[ i ][ j ] =
{ 1/(k+1),if i = 0 and 0 <= j <= k
{ 1/(k+1) * ( dp[i-1][j] + dp[i-1][j+1] ), if i > 0 and j = 0
{ 1/(k+1) * ( dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1] ), if i > 0 and 1 <= j <= k-1
{ 1/(k+1) * ( dp[i-1][j-1] + dp[i-1][j] ), if i > 0 and j = k
代表當長度為 i+1 且結尾為 j 的字串出現的機率
TAG:DP
注意:可以利用滾動數組來降低空間複雜度
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽