Generate prefix sum of the matrix
int [ , ] prefsum = new int [ n , m ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int x = 0 ; x < m ; x ++ ) { if ( x == 0 ) prefsum [ i , x ] = grid [ i , x ] ; else prefsum [ i , x ] = prefsum [ i , x - 1 ] + grid [ i , x ] ; } } int [ , ] dp = new int [ n , X + 1 ] ;