Approach 1: Dynamic Programming
This problem has an optimal substructure, meaning that the solutions to subproblems can be used to solve larger instances of this problem. This makes dynamic programming an ideal candidate.
dp(r, c) be the minimum total weight of a falling path starting at
(r, c) and reaching the bottom row.
dp(r, c) = A[r][c] + min(dp(r+1, c-1), dp(r+1, c), dp(r+1, c+1)), and the answer is .
Usually, we would make an auxillary array
dp to cache intermediate values
dp(r, c). However, this time we will use
A to cache these values. Our goal is to transform the values of
A into the values of
We process each row, starting with the second last. (The last row is already correct.) We set
A[r][c] = min(A[r+1][c-1], A[r+1][c], A[r+1][c+1]), handling boundary conditions gracefully.
Let's look at the recursion a little more to get a handle on why it works. For an array like
A = [[1,1,1],[5,3,1],[2,3,4]], imagine you are at
(1, 0) (
A = 5). You can either go to
(2, 0) and get a weight of 2, or
(2, 1) and get a weight of 3. Since 2 is lower, we say that the minimum total weight at
(1, 0) is
dp(1, 0) = 5 + 2 (5 for the original
(1, 1), and
A [which is storing the values of our
dp], looks like
[[1,1,1],[7,5,4],[2,3,4]]. We do this procedure again by visiting
(0, 2). We get
A = [[6,5,5],[7,5,4],[2,3,4]], and the final answer is
min(A) = 5
Time Complexity: , where is the length of
Space Complexity: in additional space complexity.
Analysis written by: @awice.