專欄：50多種數據結構徹底征服
專欄：50多種經典圖論算法全部掌握
搞不明白公司刷KPI的目的是什么？這玩意能提高公司的利潤嗎？還是給hr練練手？我記得在2019年找工作的時候也遇到過一次，路程一個多小時，面了兩輪問的我都回答上來了，我感覺我回答的是無可挑剔，結果他又看了簡歷說了句：我們不需要這么長工作經驗的，想招個一兩年的，一句話把我打發(fā)走了。
走在路上越想越不對，簡歷上明明寫的有工作時間，如果不需要那么長工作經驗，為什么還要叫我過來面試，當時真想把簡歷砸在他臉上。但是又感覺比那些讓你回去等通知的要真誠一些，因為讓你回去等通知，你不確定到底是自己能力不行還是來刷KPI的。但不管怎么說，讓人過來刷KPI的真的讓人很反感，不知道這么做能給公司帶來什么？
--------------下面是今天的算法題--------------
來看下今天的算法題，這題是LeetCode的第1289題：下降路徑最小和 II，難度是困難。
給你一個 n x n 整數矩陣 grid ，請你返回非零偏移下降路徑數字和的最小值。
非零偏移下降路徑定義為：從 grid 數組中的每一行選擇一個數字，且按順序選出來的數字中，相鄰數字不在原數組的同一列。
示例1：
輸入：grid = [[1,2,3],[4,5,6],[7,8,9]] 輸出：13 解釋： 所有非零偏移下降路徑包括： [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] 下降路徑中數字和最小的是 [1,5,7] ，所以答案是 13 。
n == grid.length == grid[i].length
1 <= n <= 200
-99 <= grid[i][j] <= 99
問題分析
這題說的是從二維數組的第一行開始，每行選擇一個數字，一直到最后一行，問選擇的數字最小和是多少，并且在相鄰的兩行中，選擇的數字不能在同一列，比如說第 i 行選擇了grid[i][j]，那么下一行就不能選擇grid[i+1][j]。
這題是一道典型的動態(tài)規(guī)劃問題，我們定義dp[i][j]表示從第一行開始一直到第 i 行，且第 i 行選擇的是grid[i][j]，所選擇的最小數字和。
當上面一行選擇數字grid[i-1][j]的時候，那么當前行可以選擇除grid[i][j]以外的任何數字，所以 dp[i][j] = min(dp[i - 1][k] + grid[i][j])；其中 k 是枚舉上一行除了第 j 列的所有數字。
對于第一行由于上面沒有數字，所以第一行可以選擇任何數字，也就是： dp[0][i] = grid[0][i]；最終答案是取最后一行dp[n-1][j]的最小，其中0<=j
JAVA：
public int minFallingPathSum(int[][] grid) { int n = grid.length; // dp[i][j]表示從最上面一行到grid[i][j]得到的路徑最小和。 int[][] dp = newint[n][n]; // 求最小值，默認先給一個最大值。 for (int i = 0; i < n; i++) Arrays.fill(dp[i], Integer.MAX_VALUE); // 第一行沒法從上面下來，直接初始化。 for (int i = 0; i < n; i++) dp[0][i] = grid[0][i]; for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { // 從上一行的第 k 列到dp[i][j]。 for (int k = 0; k < n; k++) { if (j == k)// 當前行不能和上一行選擇同一列。 continue; dp[i][j] = Math.min(dp[i][j], dp[i - 1][k] + grid[i][j]); } } } // 取最小面一行的最小值。 int ans = Integer.MAX_VALUE; for (int j = 0; j < n; j++) ans = Math.min(ans, dp[n - 1][j]); return ans; }C++：
public: int minFallingPathSum(vector
> &grid) { int n = grid.size(); // dp[i][j]表示從最上面一行到grid[i][j]得到的路徑最小和。 vector
> dp(n, vector
(n, INT_MAX)); // 第一行沒法從上面下來，直接初始化。 for (int i = 0; i < n; i++) dp[0][i] = grid[0][i]; for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { // 從上一行的第 k 列到dp[i][j]。 for (int k = 0; k < n; k++) { if (j == k)// 當前行不能和上一行選擇同一列。 continue; dp[i][j] = min(dp[i][j], dp[i - 1][k] + grid[i][j]); } } } // 取最小面一行的最小值。 int ans = INT_MAX; for (int j = 0; j < n; j++) ans = min(ans, dp[n - 1][j]); return ans; }
筆者簡介
博哥，真名：王一博，畢業(yè)十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。
熱門跟貼