3651. 帶傳送的最小路徑成本

困難最短路徑堆動態規劃

小貼士：第二個方法比較好，第一個方法主要是思考過程。

Dijkstra

最初直覺想到動態規劃，但因為題目允許傳送，且方向不固定，
產生了「後無效性」，或是環的情況，打破了 DP 的計算順序。
（雖然後面發現並不是這麼一回事）

最後打算用最短路徑演算法去解決這道問題，因為邊的權重沒有負數，用Dijkstra演算法。

為了處理「最多 $k$ 次傳送的限制」。

定義狀態dist[x][y][k]：代表走到座標 $(x,y)$ 且使用了 $k$ 次傳送的最小成本。
Priority Queue：{cost, x, y, used_k}，按照 cost 從小到大排序。

有兩種擴展路徑的方式

普通移動：往下或往右。
- 成本：cost + grid[x][y]
- 狀態變化：used[k]不變
傳送移動：
- 成本不變
- 狀態變化：used[k]++
- 需要找到滿足的目標點target，這個點的成本要比當前點小，如果暴力搜尋會超時。

優化一：排序跟雙指針
- 將所有格子放入sorted_cell中，並按照成本從小到大排序。
- 維護ptrs陣列，記錄每一層used_k目前在sorted_cell掃描到的位置。
- 每次都掃描直到不滿足條件，因為拿出的節點成本只會越來越多，
  能透過傳送訪問到的位置只會越來越靠後。如果上次可以訪問到的節點，
  在排序好的列表當中在pos，那麼，在後來再度嘗試傳送時，
  只需要從pos開始往後，直到成本要大於自己之後結束就好，
  至於pos前面的所有節點, 就算現在選擇使用傳送過去，
  當前的高成本也註定代表這條路徑不是最好的。
優化二：
- 問題：堆中可能存在同一個狀態的多種版本
- 解法：從堆中取出的點，檢查是否比dist陣列中的數值大，如果比較大，表示為舊資料，不需進行後續計算。
優化三：
- 問題：當傳送到(nx, ny)且狀態為used_k + 1時，
  如果之前已經有「更少傳送次數」且成本更低的路徑到過這裡，那這次傳送就是浪費。
- 解法：在把傳送結果加入堆前檢查。

程式碼

class Solution {
public:
    int minCost(vector<vector<int>>& grid, int k) {
        using t4i = tuple<int, int, int, int>;
        int m = grid.size(), n = grid[0].size();
        vector<tuple<int, int, int>> sorted_cell; // cost, 座標
        priority_queue<t4i, vector<t4i>, greater<t4i>> pq; // cost, 座標, 技能使用次數
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                sorted_cell.push_back(make_tuple(grid[i][j], i, j));
            }
        }
        ranges::sort(sorted_cell);
        pq.push(make_tuple(0, 0, 0, 0)); // 起點的成本不需要計算
        
        vector dist(m, vector(n, vector(k + 1, INT_MAX))); // dist[x][y][k] = cost
        dist[0][0][0] = 0;
        vector<int> ptrs(k + 1, 0); // 紀錄技能使用次數對應走訪到的位置
        while(!pq.empty()) {
            auto [cost, x, y, used_k] = pq.top(); pq.pop();
            if(cost > dist[x][y][used_k]) continue; // 優化二
            
            // 正常移動, 可以移動到自己的兩個鄰居
            if(x + 1 < m && dist[x + 1][y][used_k] > cost + grid[x + 1][y]) {
                dist[x + 1][y][used_k] = cost + grid[x + 1][y];
                pq.push(make_tuple(cost + grid[x + 1][y], x + 1, y, used_k));
            }
            if(y + 1 < n && dist[x][y + 1][used_k] > cost + grid[x][y + 1]) {
                dist[x][y + 1][used_k] = cost + grid[x][y + 1];
                pq.push(make_tuple(cost + grid[x][y + 1], x, y + 1, used_k));
            }
            
            // 傳送移動
            if(used_k + 1 <= k) { // 還可以用技能
                while(ptrs[used_k] < m * n) { // 指針還可以往前走
                    auto [_, nx, ny] = sorted_cell[ptrs[used_k]];
                    // 優化三：檢查 dist[nx][ny][0...used_k] 的最小值
                    if(ranges::min(dist[nx][ny] | views::take(used_k + 1)) <= dist[x][y][used_k]) {
                        ptrs[used_k]++;
                        continue;
                    }
                    if(grid[nx][ny] <= grid[x][y]) {
                        if(dist[nx][ny][used_k + 1] > dist[x][y][used_k]) {
                            dist[nx][ny][used_k + 1] = dist[x][y][used_k];
                            pq.push(make_tuple(dist[nx][ny][used_k + 1], nx, ny, used_k + 1));
                        }
                        ptrs[used_k]++;
                    }
                    else { // 當前指針的成本大過自己，無法傳送
                        break;
                    }
                }
            }
        }
        return ranges::min(dist[m - 1][n - 1]);
    }
};

複雜度分析

時間複雜度： $O(mn\times \max_{k}\times \log(mn\times \max_{k}))$
空間複雜度： $O(mn\times \max_{k})$

動態規劃

前置題目：64. 最小路徑和

因為傳送次數會影響到能不能繼續傳送，原先的 dp 矩陣需要多一個維度，
定義 dp[t][i][j] 代表走到 $(i,j)$ 且使用了 $t$ 次傳送的最小成本。
根據題目規則，如果想要從 $(r, c)$ 傳送到 $(i, j)$ ，這兩個格子需要滿足以下條件

$grid[r][c]\geq grid[i][j]$

如果滿足條件，傳送是免費的，那麼傳送過來的轉移方程就是

dp[t][i][j] = \min(dp[t][i][j], dp[t-1][r][c])

如果要算出某個特定格子 $(i,j)$ 的值，就需要去地圖上檢查所有滿足條件的格子，然後挑一個 $dp[t-1]$ 最小的。

地圖上有 $M\times N$ 個格子。
每一個格子都要去檢查 $M\times N$ 個格子，
暴力搜索會是 $O(MN)^2$ ，會超時。

在找最佳傳送來源 $(r,c)$ 時，完全不需要在乎它的座標，而只在乎兩件事。

它的數值必須 $\geq$ 我現在的數值
它的成本 $dp[t-1]$ 越小越好

如果把上一輪 $(t-1)$ 算出來的所有結果，
依照「格子的數值」整理起來，存到一個陣列 min_f 中

min_f[5] = 上一輪所有數值為 5 的格子中，最小的成本。
min_f[6] = 上一輪所有數值為 6 的格子中，最小的成本。
$\dots$

那麼，當站在一個數值為 $X$ 的格子上，想要找傳送來源時，
就從min_f[X]到min_f[k]找最小值即可。

最後一個問題，如果在計算每一個格子 $(i,j)$ 的最小成本時，都需要遍歷去算，會有大量的重複部分。
這部分能用「前綴最小值」來優化。

如果在每一輪移動結束後，從後往前遍歷一次min_f陣列，轉換成suf_min陣列。

suf_min[1000] = min_f[1000]
suf_min[999] = min(min_f[999], suf_min[1000])
suf_min[998] = min(min_f[998], suf_min[999])
$\dots$

這樣，當站在一個數值為 $X$ 的格子上，想要找傳送來源時，直接查suf_min[X]即可。

程式碼

class Solution {
public:
    int minCost(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();        
        int mx = 0;
        for (auto& row : grid) mx = max(mx, ranges::max(row));

        // suf_min[v]: 能夠「直接查詢」的最佳傳送成本
        // 大小設為 mx + 2 是為了處理邊界 (i+1 不會越界)
        vector<int> suf_min(mx + 2, INT_MAX);
        
        // min_f[v]: 用來「收集數據」的陣列
        vector<int> min_f(mx + 1);
        
        // f[j]: 代表走到當前這一列第 j-1 格的最小成本 (1-based indexing)
        // 大小 n+1，f[j+1] 對應 grid[][j]
        vector<int> f(n + 1);

        for (int t = 0; t <= k; t++) {
            ranges::fill(min_f, INT_MAX);
            ranges::fill(f, INT_MAX / 2);
            // 起點 (0,0) 的初始狀態
            // 這裡對應 f[1] (代表 grid column 0)
            if (t == 0) f[1] = -grid[0][0]; 
            for (auto& row : grid) {
                for (int j = 1; j <= n; j++) {
                    int x = row[j - 1]; // 當前格子的數值
                    int walk_cost = min(f[j - 1], f[j]) + x;
                    // 計算「傳送」過來的成本 (直接查表)
                    int teleport_cost = suf_min[x];                    
                    // 結合兩者，並更新 f[j+1]
                    f[j] = min(walk_cost, teleport_cost);                    
                    // 收集數據給下一輪用
                    min_f[x] = min(min_f[x], f[j]);
                }
            }
            // 計算後綴最小值
            for(int i = mx; i >= 0; i--) {
                suf_min[i] = min(min_f[i], suf_min[i + 1]);
            }
        }

        return f[n];
    }
};

複雜度分析

時間複雜度： $O(mn\times \max_{k})$
空間複雜度： $O(mn\times \max_{k})$

3651. 帶傳送的最小路徑成本

Dijkstra

程式碼

複雜度分析

動態規劃

程式碼

複雜度分析

顯示設定