931. Minimum Falling Path Sum
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.
2. 題目分析
在一個n階矩陣中,從第一行的任一進制素開始,找到到達最後一行時的最短路徑,但要求,選擇路徑中的下一個元素,必須與目前元素的距離不超過1,即如果目前元素處于(i.j),則下一個元素隻能是(i+1,j-1),(i+1,j),(i+1,j+1)中的一個。
3. 解題思路
這題其實與找在m*n矩陣中從一個元素開始到達最右下角元素的最短路徑的題型差不多,隻是行走規則和到達的目的地不一樣而已。是以都是動态規劃的題目。按照我之前分析的動态規劃的思路:
- 首先确定狀态,用dp[i][j]表示到達第i行第j列時的最小路徑(從第0行開始);
- 初始化,對第0行的是以狀态進行初始化,即dp[0][j] = A[0][j];
- 找狀态轉移方程,因為到達(i,j),隻可能是(i-1,j-1),(i-1,j),(i-1,j+1)這三個點,是以隻要比較這三者,找到最小值就行,需要注意的是,如果目前i=0,則,沒喲j-1;如果目前i=length-1;則沒有j+1。
4. 代碼實作(java)
package com.algorithm.leetcode.dynamicAllocation;
/**
* Created by 淩 on 2019/1/27.
* 注釋:931. Minimum Falling Path Sum
*/
public class MinFallingPathSum {
public int minFallingPathSum(int[][] A) {
int len = A.length;
if (A == null || len == 0){
return 0;
}
int[][] dp =new int[len][len];
for (int j = 0; j < len; j++) {
dp[0][j] = A[0][j];
}
for (int i = 1; i < len; i++) {
for (int j = 0; j < len; j++) {
dp[i][j] = dp[i-1][j];
if (j>=1){
dp[i][j] = Math.min(dp[i][j],dp[i-1][j-1]);
}
if (j+1<len){
dp[i][j] = Math.min(dp[i][j],dp[i-1][j+1]);
}
dp[i][j] += A[i][j];
}
}
int min = Integer.MAX_VALUE;
for (int j = 0; j < len; j++) {
min = Math.min(dp[len-1][j],min);
}
return min;
}
}