🚀 算法題 🚀

🌲 算法刷題專欄 | 面試必備算法 | 面試高頻算法 🍀
🌲 越難的東西,越要努力堅持，因為它具有很高的價值，算法就是這樣?
🌲 作者簡介：碩風和煒，CSDN-Java領域新星創作者🏆，保研|國家獎學金|高中學習JAVA|大學完善JAVA開發技術棧|面試刷題|面經八股文|經驗分享|好用的網站工具分享💎💎💎
🌲 恭喜你發現一枚寶藏博主,趕快收入囊中吧🌻
🌲 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？🎯🎯

🚀 算法題 🚀

🚩 題目鏈接

• 2304. 網格中的最小路徑代價

? 題目描述

給你一個下標從 0 開始的整數矩陣 grid ，矩陣大小為 m x n ，由從 0 到 m * n - 1 的不同整數組成。你可以在此矩陣中，從一個單元格移動到 下一行 的任何其他單元格。如果你位于單元格 (x, y) ，且滿足 x < m - 1 ，你可以移動到 (x + 1, 0), (x + 1, 1), …, (x + 1, n - 1) 中的任何一個單元格。注意： 在最后一行中的單元格不能觸發移動。

每次可能的移動都需要付出對應的代價，代價用一個下標從 0 開始的二維數組 moveCost 表示，該數組大小為 (m * n) x n ，其中 moveCost[i][j] 是從值為 i 的單元格移動到下一行第 j 列單元格的代價。從 grid 最后一行的單元格移動的代價可以忽略。

grid 一條路徑的代價是：所有路徑經過的單元格的 值之和 加上 所有移動的 代價之和 。從 第一行 任意單元格出發，返回到達 最后一行 任意單元格的最小路徑代價。

示例 1：

輸入：grid = [[5,3],[4,0],[2,1]], moveCost = [[9,8],[1,5],[10,12],[18,6],[2,4],[14,3]]
輸出：17
解釋：最小代價的路徑是 5 -> 0 -> 1 。

• 路徑途經單元格值之和 5 + 0 + 1 = 6 。
• 從 5 移動到 0 的代價為 3 。
• 從 0 移動到 1 的代價為 8 。
  路徑總代價為 6 + 3 + 8 = 17 。
  示例 2：

輸入：grid = [[5,1,2],[4,0,3]], moveCost = [[12,10,15],[20,23,8],[21,7,1],[8,1,13],[9,10,25],[5,3,2]]
輸出：6
解釋：
最小代價的路徑是 2 -> 3 。

• 路徑途經單元格值之和 2 + 3 = 5 。
• 從 2 移動到 3 的代價為 1 。
  路徑總代價為 5 + 1 = 6 。

提示：

m == grid.length
n == grid[i].length
2 <= m, n <= 50
grid 由從 0 到 m * n - 1 的不同整數組成
moveCost.length == m * n
moveCost[i].length == n
1 <= moveCost[i][j] <= 100

🌟 求解思路&實現代碼&運行結果

---

? dijkstra(迪杰斯特拉)

🥦 求解思路

1. 該題通過迪杰斯特拉算法求解即可，但是需要注意的是，我們需要找到一個開始的節點位置，以及結束的位置，因為題目中給定的是可以從第一行任意節點開始，到達最后一行任意節點，這個過程通過設置倆個虛擬的節點解決。
2. 其它的過程就是dijkstra基本求解過程。
3. 具體實現代碼如下：
4. 需要注意的是，該題還可以通過dp來做，后續補充。敬請期待。

🥦 實現代碼

class Solution {public int minPathCost(int[][] grid, int[][] moveCost) {int m=grid.length,n=grid[0].length;int[][] map=new int[m*n+2][m*n+2];for(int i=0;i<map.length;i++) Arrays.fill(map[i],Integer.MAX_VALUE/2);int start=m*n;for(int j=0;j<n;j++){int to=grid[0][j];map[start][to]=0+to;}for(int i=0;i<m-1;i++){for(int j=0;j<n;j++){int from=grid[i][j];for(int k=0;k<n;k++){int to=grid[i+1][k];map[from][to]=moveCost[from][k]+to;}}}for(int j=0;j<n;j++){int from=grid[m-1][j];map[from][n*m+1]=0;}int[] ans=dijkstra(grid,map,moveCost,start);for(int v:ans){System.out.println(v);}return ans[n*m+1];}public int[] dijkstra(int[][] grid,int[][] map,int[][] moveCost,int start){int m=grid.length,n=grid[0].length;PriorityQueue<int[]> queue=new PriorityQueue<>((a,b)->a[1]-b[1]);queue.add(new int[]{start,0});boolean[] flag=new boolean[m*n+2];Arrays.fill(flag,false);int[] dist=new int[m*n+2];Arrays.fill(dist,Integer.MAX_VALUE/2);dist[m*n]=0;while(!queue.isEmpty()){int[] arr=queue.poll();int next=arr[0],cost=arr[1];if(flag[next]) continue;flag[next]=true;for(int ne=0;ne<=m*n+1;ne++){if(map[next][ne]+dist[next]<dist[ne]){dist[ne]=map[next][ne]+dist[next];queue.add(new int[]{ne,dist[ne]});}}}return dist;}
}

🥦 運行結果

---

💬 共勉

最后，我想和大家分享一句一直激勵我的座右銘，希望可以與大家共勉！