題意: 有 n 個身高皆不同的人排成一排，問左邊看到 p 個人，右邊能看到 r 個人，問有幾種排列可能。
解法: 要找排列情況可聯想 DP，所以想辦法想出遞迴方程，想像當總人數為 n' 個人，左邊看的到 p' 個人，右邊看的到 r' 個人，想把最矮的人拿掉的所有情況，假設最矮的人站在第一個位子，那拿掉他之後從左邊看就會少一個人，如果最矮的人站在最後一個位子，拿掉他後從右邊看也會少一個，如果最矮的人站在中間任何一個位子，拿掉他之後，從左邊或右邊看人數不變。
dp[n'][p'][r'] =
{ 1, if n' = p' = r' = 1
{ dp[n'-1][p'-1][r'] + dp[n'-1][p'][r'] + dp[n'-1][p'][r'-1], if n' > 1, 1 <= p', r' <= n'
TAG: DP
注意:
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽