1. 題目

給你一個整數方陣 arr ，定義「非零偏移下降路徑」為：從 arr 數組中的每一行選擇一個數字，且按順序選出來的數字中，相鄰數字不在原數組的同一列。

請你返回非零偏移下降路徑數字和的最小值。

示例 1： 輸入：arr = [[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 。提示： 1 <= arr.length == arr[i].length <= 200 -99 <= arr[i][j] <= 99

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-falling-path-sum-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 動態規劃解題

class Solution { public:int minFallingPathSum(vector<vector<int>>& arr) {int m = arr.size(), n = arr[0].size();if(n == 1)//一列，不滿足題目要求return 0;vector<int> dp(arr[0]);//存儲到達每一行的最小路徑和，第一行初始為arr數值vector<int> temp(n,INT_MAX);int i, j, k, MIN = INT_MAX;for(i = 1; i < m; i++)//從第2行開始{for(j = 0; j < n; j++)temp[j] = INT_MAX;//臨時存儲最小路徑和，初始化為INT_MAXfor(j = 0; j < n; j++)//對上一行的每個dp[j] 計算下一行的 dp值{ for(k = 0; k < n; k++){if(k == j)//不同列的要求continue;temp[k] = min(temp[k], dp[j]+arr[i][k]);//第j列可以選擇下一行的 k列作為路徑} }for(j = 0; j < n; j++)dp[j] = temp[j];//臨時值存入dp中，狀態壓縮}for(i = 0; i < n; i++)if(dp[i] < MIN)MIN = dp[i];//取最后一行的最小值return MIN;} };

總結

以上是生活随笔為你收集整理的LeetCode 1289. 下降路径最小和 II（DP）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。