目錄
題目
題目解析
思路
1.狀態表示
2.狀態轉移方程
3.初始化
4.填表順序
5.返回值
代碼
題目
931. 下降路徑最小和
給你一個?n x n?的?方形?整數數組?matrix?，請你找出并返回通過?matrix?的下降路徑?的?最小和?。
下降路徑?可以從第一行中的任何元素開始，并從每一行中選擇一個元素。在下一行選擇的元素和當前行所選元素最多相隔一列（即位于正下方或者沿對角線向左或者向右的第一個元素）。具體來說，位置?(row, col)?的下一個元素應當是?(row + 1, col - 1)、(row + 1, col)?或者?(row + 1, col + 1)?。
示例 1：
輸入：matrix = [[2,1,3],[6,5,4],[7,8,9]] 輸出：13 解釋：如圖所示，為和最小的兩條下降路徑
示例 2：
輸入：matrix = [[-19,57],[-40,-5]] 輸出：-59 解釋：如圖所示，為和最小的下降路徑
提示：
n == matrix.length == matrix[i].length1 <= n <= 100-100 <= matrix[i][j] <= 100
題目解析
????????題目是給一個n*n的矩陣，矩陣里面有值，從第一行到最后一行，所走過的最小值，從第一行元素的任意一個開始，往最后一行走 ，既然是最小值，那沒每次就要挑下一行的最小值走，，而這個不是隨便挑的，是以第一行這個位置，在第二行離的最近的三個位置中跳最小的值，圖示如下圖。
????????如果第一行從1開始走，那么第二行，只能走6，5或者4。每走一步加上該位置的值就行，根據規則走到最后 一行 就算結束，返回最小的那個就行。如果是邊界，也就是只有兩個位置離它最近。
思路
1.狀態表示
????????狀態表示，我們還是選用最常用的方法——選用以某一個位置為結尾，也就是從第一行走到該位置，題目要求，最小路徑，所以狀態表示可以看成dp[i][j]——從開始走到該【i，j】位置的最小的下降路徑。
2.狀態轉移方程
????????根據最近的一步劃分路徑，最近的路徑，到達【i，j】位置，可以從【i-1，j-1】位置，【i-1，j】或者【i-1，j+1】位置到達，所以應當分三種情況討論。
a)從【i-1，j-1】位置到達【i，j】位置
????????要得到第一行到【i，j】位置的最小路徑，就要得到第一行到【i-1，j-1】的最小路徑，然后加上【i-1，j-1】位置上面的值就是，第一行到【i，j】位置的最小值。而第一行到【i-1，j-1】位置的最小路徑可以用dp[i-1][j-1]表示，
????????所以此情況下的狀態轉移方程就是dp[i][j]=dp[i-1][j-1]+matrix[i-1][j-1]
b)從【i-1，j】位置到達【i，j】位置
????????同理，得到這個狀態轉移方程dp[i][j]=dp[i-1][j]+matrix[i-1][j]
c)從【i-1，j+1】位置到達【i，j】位置
????????同理，得到這個狀態轉移方程dp[i][j]=dp[i-1][j+1]+matrix[i-1][j+1]
然后取這三種情況的最小值。
3.初始化
????????初始化是為了讓填表的時候不要越界。我們要算第一行到指定位置的路徑最小值，也就是算dp[i][j]，根據狀態轉移方程可以看出要算dp[i][j]，要先得到dp[i-1][j],dp[i-1][j-1],dp[i-1][j+1],第一行和第一列和最后一列，這三個位置是不全的，所以要初始化第一行和第一列，最后一列的位置。
????????之前學過，虛擬節點的方式，把需要的位置補起來，填上能使結果正確的值就行，補虛擬結點的方式，如下圖所示。
????????現在要確定里面要填什么值，才能使結果正確，我們先來看不加虛擬結點的時候那里面應該填什么？
????????對于第一行，比如：dp[0][0]，dp[0][0]表示從第一行到當前位置的最小值，可以看出當前位置就是在第一行，也就是自己到自己，也就等于本身矩陣里面的值，這樣 我們將加的第一行虛擬結點賦值為0就可以不影響結果。
????????對于第一列和最后一列，對于第一列，從第二行開始，它們只是缺了左上角那個數，其他兩個都在，如果不加虛擬結點，也就是說只在這兩個結點里面挑一個最小的加上就行，也就是說 虛擬結點里面的值不能影響dp[i][j]的結果 ，虛擬結點里面的值要比其他兩個值都大，為了確保起見，應該將虛擬結點賦值為正的無窮大。
????????我們加完之后，還要解決下標映射的問題加了一行，所以就 整體向下挪了一行，左邊增加一列，也就是向右挪了一列。
????????所以當我們算dp[1][1]的值我們要用martix[0][0]值來計算。
4.填表順序
填表順序，還是從上到下，從左到右
5.返回值
因為是要到達最后一行，并且是要最小值，所以我們返回dp表中最后一行的最小值就行
代碼
????????初始化技巧：我們為了方便初始化，如果我們在定義dp表時，將所有值定義為0，后面初始化的時候要改兩列的值，所以這里可以我們一開始就將每個初始化正的無窮大。
int min(int a,int b)
{return (a<b)?a:b;
}
int minFallingPathSum(int** matrix, int matrixSize, int* matrixColSize)
{int nummin=INT_MAX;int n=matrixColSize[0];//創建一個dp表int dp[102][102]={INT_MAX};//初始化for(int i=0;i<102;i++)for(int j=0;j<102;j++){dp[i][j]=INT_MAX;}for(int j=0;j<n+2;j++)dp[0][j]=0;//填表 for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dp[i][j]=min( min(dp[i-1][j],dp[i-1][j-1]) , dp[i-1][j+1] ) +matrix[i-1][j-1];}}for(int j=1;j<=n;j++){nummin=min(nummin,dp[n][j]);}return nummin;
}空間復雜度：O()
時間復雜度：O()
)
