Maximize path sum from top | C # program to implement the above approach ; Function to get the maximum path sum from top - left cell to all other cells of the given matrix ; Store the maximum path sum ; Base case ; Compute the value of dp [ i , j ] using the recurrence relation ; Print maximum path sum from the top - left cell ; Driver Code
using System ; class GFG { static readonly int SZ = 100 ; static void pathSum ( int [ , ] mat , int N , int M ) { int [ , ] dp = new int [ N , M ] ; dp [ 0 , 0 ] = mat [ 0 , 0 ] ; for ( int i = 1 ; i < N ; i ++ ) { dp [ i , 0 ] = mat [ i , 0 ] + dp [ i - 1 , 0 ] ; } for ( int j = 1 ; j < M ; j ++ ) { dp [ 0 , j ] = mat [ 0 , j ] + dp [ 0 , j - 1 ] ; } for ( int i = 1 ; i < N ; i ++ ) { for ( int j = 1 ; j < M ; j ++ ) { dp [ i , j ] = mat [ i , j ] + Math . Max ( dp [ i - 1 , j ] , dp [ i , j - 1 ] ) ; } } for ( int i = 0 ; i < N ; i ++ ) { for ( int j = 0 ; j < M ; j ++ ) { Console . Write ( dp [ i , j ] + " ▁ " ) ; } Console . WriteLine ( ) ; } } public static void Main ( String [ ] args ) { int [ , ] mat = { { 3 , 2 , 1 } , { 6 , 5 , 4 } , { 7 , 8 , 9 } } ; int N = 3 ; int M = 3 ; pathSum ( mat , N , M ) ; } }