APCS
老鼠在地圖的左上角 (0, 0),只能向右或向下移動,最終要到達右下角 (N-1, M-1)。每走一格都會消耗體力值,消耗的體力值等於該格的數字。題目要求我們找到從起點到終點的所有可能路徑中,體力消耗最少的那條路徑,並輸出其總體力消耗值。
這個問題的解題關鍵在於使用動態規劃:
route
,其中 route[i][j]
表示從左上角 (0, 0)
到達該格 (i, j)
的最小體力消耗值。(i, j-1)
,則 route[i][j] = route[i][j-1] + grid[i][j]
。(i-1, j)
,則 route[i][j] = route[i-1][j] + grid[i][j]
。route[i][j] = min(route[i-1][j], route[i][j-1]) + grid[i][j]
,這表示老鼠應該選擇從體力消耗較小的那條路徑來到 (i, j)
。route[0][j] = route[0][j-1] + grid[0][j]
。route[i][0] = route[i-1][0] + grid[i][0]
。route[N-1][M-1]
,即從 (0, 0)
到達 (N-1, M-1)
的最小體力消耗值。