Re: [排組] 一題限制轉彎次數的捷徑問題

[mantour (朱子)]

※ 引述《wayne0824 (萊恩)》之銘言：
: http://i.imgur.com/iXwDeqB.jpg
: 如題，除了要討論在P以前和P以後的轉彎次數，還要考慮在P點是否有轉彎    想請問各位有其他想法嗎？
: 題目出自高雄女中補充教材
: -----
: Sent from JPTT on my iPhone

對每一點Q(x,y)定義一個2x5矩陣 M(x,y,i,j), i=1~2, j=0~4

M(x,y,1,j) = 到達該點剛好轉j次，且最後一步向右的走法數
M(x,y,2,j) = 到達該點剛好轉j此，且最後一步向上的走法數

則有以下關係

M(x,y,1,j) = 到達 Q'(x-1,y) 剛好轉j次，且最後一步向右的走法數
            +到達 Q'(x-1,y) 剛好轉j-1次，且最後一步向上的走法數
           = M(x-1,y,1,j) + M(x-1,y,2,j-1)

同理

M(x,y,2,j) = M(x,y-1,1,j-1) + M(x,y-1,2,j)

以上二式疊代從左下角開始往右上角填上各點的矩陣，注意在禁止路徑上的各點值皆為0

可得下圖

http://imgur.com/a/Qionh

得解從A經過P到達B走捷徑

剛好轉2次有  1+1  = 2 種走法
剛好轉3次有  5+5  = 10種走法
剛好轉4次有 19+13 = 32種走法

這個解法有點類似演算法裡面的動態規劃
可以同時一次解出B點以外到達各點，轉不同次數的走法數

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.225.221.208
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1491751859.A.DF3.html
※ 編輯: mantour (36.225.221.208), 04/09/2017 23:35:22
推 Desperato   : 推推