Minimum sum falling path in a NxN grid | Java Program to minimum required sum ; Function to return minimum path falling sum ; R = Row and C = Column We begin from second last row and keep adding maximum sum . ; best = min ( A [ R + 1 ] [ C - 1 ] , A [ R + 1 ] [ C ] , A [ R + 1 ] [ C + 1 ] ) ; Driver program ; function to print required answer
import java . io . * ; class GFG { static int n = 3 ; static int minFallingPathSum ( int A [ ] [ ] ) { for ( int R = n - 2 ; R >= 0 ; -- R ) { for ( int C = 0 ; C < n ; ++ C ) { int best = A [ R + 1 ] [ C ] ; if ( C > 0 ) best = Math . min ( best , A [ R + 1 ] [ C - 1 ] ) ; if ( C + 1 < n ) best = Math . min ( best , A [ R + 1 ] [ C + 1 ] ) ; A [ R ] [ C ] = A [ R ] [ C ] + best ; } } int ans = Integer . MAX_VALUE ; for ( int i = 0 ; i < n ; ++ i ) ans = Math . min ( ans , A [ 0 ] [ i ] ) ; return ans ; } public static void main ( String [ ] args ) { int A [ ] [ ] = { { 1 , 2 , 3 } , { 4 , 5 , 6 } , { 7 , 8 , 9 } } ; System . out . println ( minFallingPathSum ( A ) ) ; } }