Minimum Falling Path

Solve the leetcode problem #931

Introduction

 

In this article, we will sove the leetcode problem #931, Minimum Falling Path Sum. The problem statement goes like this: Given a square array of integers A, we want the minimum sum of a falling path through A. A falling path starts at any element in the first row, and chooses one element from each row. The next row's choice must be in a column that is different from the previous row's column by at most one. There are a few examples listed below which might help to elaborate on the problem:

static void Main(string[] args)
{
    var result = minFallingPathSum(new int[,]
    {
        { 1, 2, 3 },
        { 4, 5, 6 },
        { 7, 8, 9 }
    });
}

The possible paths for A [[1,2,3],[4,5,6],[7,8,9]] are [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9] [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9] [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9] where the falling path with the smallest sum is [1,4,7], so the answer is 12.

 

Solution

 

The most naive approach to this problem is by looping over every element and then find the possible paths and store the sum in an array. And finally find the least value from the stored array as the least path sum or the falling path needed. Given below is the C# code for the approach,

static int minFallingPathSum(int[,] A)
{
    int size = A.GetLength(0);
    int[,] dp = new int[size, size];
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size; j++)
        {
            if (i == 0)
                dp[i, j] = A[i, j];
            else
            {
                int lastRow = dp[i - 1, j];
                if (j - 1 >= 0)
                    lastRow = Math.Min(dp[i - 1, j - 1], lastRow);

                if (j + 1 < size)
                    lastRow = Math.Min(dp[i - 1, j + 1], lastRow);
                dp[i, j] = lastRow + A[i, j];
            }
        }
    }
    int minSum = int.MaxValue;
    for (int i = 0; i < size; i++)
        minSum = Math.Min(minSum, dp[size - 1, i]);
    return minSum;
}