題目：
對於一個長度為N，由0 ~ K(0 <= K <= 9)的數字組成的序列
定義如果這個序列是「緊密的」，則序列中任意兩個相鄰的數字之值皆不超過1
例如123、4565是緊密的，反之，312、4235則不是
今給定K, N，求長度為N、由0 ~ K組成的所有序列中，「緊密的」占比多少。
做法：
定義dp[i][j] = 以j結尾、長度為i的序列中，緊密的佔所有長度為i的序列之比
一開始，長度為1的序列都是緊密的，dp[1][0~k] = 1 / (k+1)
而長度每增加一，尾巴又會多接一個數字
即可以推出: dp[i][j] = ( dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1] ) / (k+1)
最後將所有長度為n的答案即dp[n][0~k]加起來，就會是答案了，記得*100轉成百分比
實作時，避免處理0和k結尾的邊界問題，寫法可以把數字平移到1~k+1，顯然不影響答案
code:
沒有留言:
張貼留言