專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

搞不明白公司刷KPI的目的是什么？這玩意能提高公司的利潤嗎？還是給hr練練手？我記得在2019年找工作的時候也遇到過一次，路程一個多小時，面了兩輪問的我都回答上來了，我感覺我回答的是無可挑剔，結果他又看了簡歷說了句：我們不需要這么長工作經驗的，想招個一兩年的，一句話把我打發走了。

走在路上越想越不對，簡歷上明明寫的有工作時間，如果不需要那么長工作經驗，為什么還要叫我過來面試，當時真想把簡歷砸在他臉上。但是又感覺比那些讓你回去等通知的要真誠一些，因為讓你回去等通知，你不確定到底是自己能力不行還是來刷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]。

這題是一道典型的動態規劃問題，我們定義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;     }

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。