מריה בוטוסוב

נותנים מטריצה של מספרים. יש למצוא נתיב הכי זול למטה. אי אפשר לחזור אחורה, אפשר ללכת רק ישל למטה, למטה שמואלה או למטה ימינה.

Input: [[1,2,3],[4,5,6],[8,7,9]]
Output: 12, because shortest is 1->4->7

This is dynamic programming problem.

public int MinFallingPathSum(int[][] A) {
    int result = int.MaxValue;
    int rows = A.Length;
    int columns = A[0].Length;        
    if(rows == 0 || columns == 0)
        return 0;
        
    for (int row = 1; row<rows; row++) {
        for(int column = 0; column<columns; column++) { 
            if(row == 0)  continue;
            if (column == 0)
                A[row][column] += Math.Min(A[row-1][column], A[row-1][column+1] );                
            else if (column == columns-1)
                A[row][column] += Math.Min(A[row-1][column-1], A[row-1][column]);
            else
                A[row][column] += Math.Min(A[row-1][column], Math.Min(A[row-1][column-1], A[row-1][column+1]));                                
        }
    }
                
    for (int column = 0; column < columns; column++) {
        result = Math.Min(result, A[rows - 1][column]);
    }
 
    return result;        
}