主題
題目連結：
題目意譯：
現在有一條長度 n 的三線道，其由 n + 1 個編號為 0 到 n 的點所組成。有一隻青蛙一開始位於第二線的第 0 點，而牠想要跳到第 n 點。不過，在路上可能有一些障礙物存在。
你被給定一個長度為 n + 1 的陣列 obstacles，其中 obstacles[i]（其值介於 0 到 3，含端點）代表著在第 obstacles[i] 線上的第 i 點上有一個障礙物。如果 obstacles[i] == 0，則代表第 i 點沒有障礙物。在每一個點上，三條線道中最多只會有一條有障礙物。
例如，如果 obstacles[2] == 1，則其代表著在第一線的第 2 點上有一個障礙物。
該青蛙只能在同一線道的第 i + 1 點上沒有障礙物時才得以從第 i 點跳到同一線道的第 i + 1 點。為了避開障礙物，該青蛙也可以側跳來跳到另一條線道的同一點上（即便兩線道必不相鄰），前提是目標線道上沒有障礙物。
例如說，青蛙可以從第三線的第 3 點跳到第一線的第 3 點。
回傳該青蛙從第二線的第 0 點抵達任一線道的第 n 點上最少所需的側跳次數。
注：第 0 點和第 n 點上不會有障礙物存在。
限制：
obstacles.length == n + 1
1 ≦ n ≦ 5 × 10 ^ 5
0 ≦ obstacles[i] ≦ 3
obstacles[0] == obstacles[n] == 0
範例測資：
範例 1：
輸入： obstacles = [0,1,2,3,0]
輸出： 2
解釋： 最佳解由上圖中的箭頭所示。當中有兩次側跳（紅色箭頭）。
注意到該青蛙只能在側跳時跳過障礙物（參見上圖中的第 2 點）。
範例 2：
輸入： obstacles = [0,1,1,3,3,0]
輸出： 0
解釋： 第二線上沒有障礙物。不需要任何的側跳。
範例 3：
輸入： obstacles = [0,2,1,0,3,0]
輸出： 2
解釋： 最佳解由上圖中的箭頭所示。當中有兩次側跳。
解題思維：
只要畫一個類似這題的狀態圖（這部分交給讀者，因為情況有點多）便可以得出這題用動態規劃解所需的遞迴式。
定義一個二維陣列 D，其中 D[i][j] 代表著在青蛙從起點跳到第 j 線第 i 點所需的最少側跳次數。可以看到：
D[0][2] = 0（起點）
D[0][1] = D[0][3] = 1（起點兩邊的線）、
如果 obstacles[i] == 1，則：
D[i][1] = 無限大（因為青蛙到不了）、
D[i][2] = min(D[i - 1][2], D[i - 1][3] + 1)（即直接從第 2 線第 i - 1 點跳過來，或是先從第 3 線第 i - 1 點跳到第 3 線第 i 點再跳過來）
D[i][3] = min(D[i - 1][3], D[i - 1][2] + 1)
如果 obstacles[i] == 2，則：
D[i][1] = min(D[i - 1][1], D[i - 1][3] + 1)
D[i][2] = 無限大
D[i][3] = min(D[i - 1][3], D[i - 1][1] + 1)
如果 obstacles[i] == 3，則：
D[i][1] = min(D[i - 1][1], D[i - 1][2] + 1)
D[i][2] = min(D[i - 1][2], D[i - 1][1] + 1)
D[i][3] = 無限大
如果 obstacles[i] == 0，則：
D[i][1] = min(D[i - 1][1], D[i - 1][2] + 1, D[i - 1][3] + 1)
D[i][2] = min(D[i - 1][2], D[i - 1][1] + 1, D[i - 1][3] + 1)
D[i][3] = min(D[i - 1][3], D[i - 1][1] + 1, D[i - 1][2] + 1)
可以看到答案會是 min(D[n][1], D[n][1], D[n][2])。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
