Code:
https://tinyurl.com/yy3a5na4
問題描述:
一維座標，每次可以往右走a格，或者往左走b格，請問走到 x 最少需要幾步。
限制:
可以連續往右走無限次a
不能連續往左走兩次b
不能走到地雷座標，如果一定會碰到地雷或是走不到x，回傳-1。
解答:
1.BFS窮舉各種走法，一步一步慢慢窮舉。
2.接著記憶化走過的點。
visited[10][0] 代表10這個點用往前走的方式走過了
visited[10][1] 代表10這個點用往後走的方式走過了
問題:
為什麼記憶化搜尋的visited要二維的，不是只要一維就好了嗎?
我想說直接visited[10] = true/false，但結果這樣會過不了測資= =
我覺得有走過的點不管是來回走過都是一樣的意義呀代表你這個點的所有可能都走過了
何必再分來回的記憶化呢?在Discuss上等不到解釋，故上來發文感恩

因為不能連續走兩次 b?

我想你應該搞錯了第二維的意思, 那個是「你用哪步來這裡」也就是它不是在記下一步而是前一步因為問題在於你的前一步是 b 時下一步不能是 b你如果沒記著是怎麼來的話下一步會不知道該不該有 b

一個用來記錄 上一步非b最少步數 一個是上一步為b最少步數 dp式推一下就會知道這樣分不能省

我回家拿那個測資失敗的例子推同額推看好了感謝我還是沒感覺感謝大大

想到一個反例了: 往右走 2, 往左走 1, 則你走不到起點以左這在你把兩種狀態混在一起時是無法得出來的結論修正: 走不到起點左一格以左如果限向右座標的話也有反例: 往右 5 往左 2, 則走不到 1

所以我們不能抹殺掉8走到6的可能感謝