# LeetCode-931. Minimum Falling Path Sum

## LeetCode-931. Minimum Falling Path Sum

Posted by Jae on June 30, 2019

### 1、题目

Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row, and chooses one element from each row. The next row’s choice must be in a column that is different from the previous row’s column by at most one.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation:
The possible falling paths are:
[1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]
[2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]
[3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]
The falling path with the smallest sum is [1,4,7], so the answer is 12.


Note:

1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100


### 2、思路

#### 2.1、确定状态

如果a[i][j]位于行首，其前一行的元素只能选m-1行的 min{a[i-1][j], a[i-1][j+1]}



##### 2.2、 状态方程

                    min{a[i-1][j], a[i-1][j+1]}     元素a[i][j]位于行首

min{a[i-1][j],[i-1][j-1]}       元素a[i][j]位于行尾


#### 2.3、 初始条件和边界情况

f[0][0] = A[0][0]
f[0][1] = A[0][1]
...
f[0][n-1] = A[0][n-1]


### 3、实现

public int minFallingPathSum(int[][] A) {
int n = A.length;
int m = A[0].length;

int[][] f = new int[n][m];
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
// 初始化
if (i == 0){
f[i][j] = A[i][j];
}else{
// 只有一列的情况
if (m == 1){
f[i][j] = A[i][j] + f[i-1][j];
continue;
}
// 第一列
if (j == 0){
f[i][j] = A[i][j] + Math.min(f[i-1][j], f[i-1][j+1]);
}else if (j == m-1){ // 最后一列
f[i][j] = A[i][j] + Math.min(f[i-1][j], f[i-1][j-1]);
}else{ // 非边界
f[i][j] = A[i][j] + Math.min(Math.min(f[i-1][j], f[i-1][j-1]), f[i-1][j+1]);
}
}
}
}
// 最优解在最后一行产生
int ans = Integer.MAX_VALUE;
for (int i = 0; i < m; i++){
ans = Math.min(ans, f[n-1][i]);
}
return ans;
}


### 5、实现

public int minFallingPathSum(int[][] A) {
int n = A.length;
int m = A[0].length;

// 开一个两行m列的数组
int[][] f = new int[2][m];
// 变量old表示前一行 now表示当前行
int old = 1;
int now = 0;

for (int i = 0; i < n; i++){
// 每次换行需要改变当前行和前一行下标
old = now;
now = 1 - now;
for (int j = 0; j < m; j++){
if (i == 0){
f[now][j] = A[i][j];
continue;
}
if (m == 1){
f[now][j] = A[i][j] + f[old][j];
}else{
if (j == 0){
f[now][j] = A[i][j] + Math.min(f[old][j], f[old][j+1]);
}else if (j == m-1){
f[now][j] = A[i][j] + Math.min(f[old][j], f[old][j-1]);
}else{
f[now][j] = A[i][j] + Math.min(Math.min(f[old][j], f[old][j-1]), f[old][j+1]);
}
}
}
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < m; i++){
ans = Math.min(ans, f[now][i]);
}
return ans;
}