我正在接受面試培訓，發現在網格中有一些石頭的網格中退出的最小成本的測驗（您不能在退出路徑中使用帶有石頭的單元格）。
我可以做這些問題，但我正在努力解決演算法的時間復雜性（作為一個整體/兩個函式）。希望這里有人可以照亮它。
我天真地猜測這是： O(4^row*col)
我們遞回地進行 DFS，在每個單元格上，我們可以分支到四個方向（上、右、下、左）。我們不會嚴格訪問每個單元格一次。
但是單元格上的值是一種記憶，不是嗎？
我的意思是遞回斐波那契，如果O(n)因為我們沒有對我們計算過的數字進行重復計算。
我們可以將每個單元格上的值計算為 Memoization 嗎？因為它在每次迭代時更新，如果它更小
func findMinStepsToExit(input [][]int) int {
if input == nil {
return -1
}
lenRow := len(input)
lenCol := len(input[0])
if lenRow == 1 && lenCol == 1 {
return 0
}
helper(input, 0, 0, lenRow, lenCol, 0)
ans := input[lenRow-1][lenCol-1]
if ans <= 1 {
return -1
}
return ans
}
func helper(grid [][]int, row, col, lenRow, lenCol, currStep int) {
if row < 0 || col < 0 || row > lenRow || col > lenCol || grid[row][cell] == 0 {
return
}
var newStep int
if grid[row][cell] != 1 {
newStep == currStep 1
if newStep > grid[row][cell] {
return
}
grid[row][cell] = newStep
}
if grid[row][cell] == 1 {
grid[row][cell] == currStep 1
}
helper(grid, row 1, col, lenRow, lenCol, currStep 1) // bottom
helper(grid, row, col 1, lenRow, lenCol, currStep 1) // right
helper(grid, row-1, col, lenRow, lenCol, currStep 1) // top
helper(grid, row, col-1, lenRow, lenCol, currStep 1) // left
return
}
uj5u.com熱心網友回復：
我認為您使用 BFS 而不是 DFS 會做得很好。（您將需要一個步驟來檢查您是否在每次迭代中踩到了石頭，而不是從那個位置走得更遠，例如通過標記它。）
如果您必須在找到出口之前檢查并標記每個單元格，則時間和空間復雜度為 O(x*y)。
這讓我想起了Dijkstra 演算法。也許看看
uj5u.com熱心網友回復：
這個演算法是指數的，不幸的是，如果你想在指數函式上得到一個嚴格的漸近界，你必須讓指數完全正確。對于這個演算法來說，這很難做到——不值得麻煩。指數太慢了。
但是單元格上的值是一種記憶，不是嗎？
確實如此，但并未得到有效利用。然而，一切都會改變，如果你做一個小小的改變，從if newStep > grid[row][cell]到if newStep >= grid[row][cell]
然后，你的演算法變成多項式。考慮到所花費的總時間與您進行的單元格更新次數成正比。由于每個單元格最初最多更新為rows*cols，然后1隨著每次更新從那里減少到最小值，因此rows*cols每個單元格最多更新一次，總時間變為 O((rows*cols) 2 )。
它仍然不是一個很好的演算法。您應該對 O(rows*cols) 使用廣度優先搜索。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/353922.html
上一篇：C#SPOJ時間優化
下一篇：雙鏈表未顯示我正在搜索的確切值