Re: [排組] 一題限制轉彎次數的捷徑問題
: 如題，除了要討論在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
推
04/09 23:41, , 1F
04/09 23:41, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 3 之 3 篇)：