Leetcode 931: Minimum falling path sum

In this problem on Leetcode, we need to compute the cost of the minimum path given the following problem:

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.

This problem is typically the sort of problems that is solved with dynamic programming. If you don’t know what dynamic programming is, no problem, we are going to go through it together. The reason you could guess it is solvable with dynamic programming is because:

1. The number of paths is exponential with the number of rows (size of the problem)
2. There is a simple recurrence relation between the cost of accessing “neighbor” spaces, making it easy to compute the cost of the minimum paths for a row given the cost of minimum paths from the previous row.

On the example provided along with the problem, we show how the algorithm work:

Step 1: Initialization of the S (solution) array with the first row of A

step 1: initialization

Step 2: Compute second row