Interview 150
Minimum Falling Path Sum
- Problem
- LC 931
- File
- interview150_LC931MinimumFallingPathSum.java
- Path
- pkg5leetcode/interview150/interview150_LC931MinimumFallingPathSum.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC931MinimumFallingPathSum.java
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/** LC 931 Minimum Falling Path Sum */4public class interview150_LC931MinimumFallingPathSum {5 static int minFallingPathSum(int[][] matrix) {6 int n = matrix.length;7 for (int r = 1; r < n; r++)8 for (int c = 0; c < n; c++) {9 int best = matrix[r-1][c];10 if (c > 0) best = Math.min(best, matrix[r-1][c-1]);11 if (c + 1 < n) best = Math.min(best, matrix[r-1][c+1]);12 matrix[r][c] += best;13 }14 int ans = matrix[n-1][0];15 for (int c = 1; c < n; c++) ans = Math.min(ans, matrix[n-1][c]);16 return ans;17 }18 19 public static void main(String[] args) {20 System.out.println(minFallingPathSum(new int[][]{{2,1,3},{6,5,4},{7,8,9}}));21 }22}