How to Determine the Base Case and Initial Values for Memoization?

Many readers have questions about the base case and initial values of the memoization in dynamic programming problems. This article specifically addresses these issues and also discusses how to guess the subtle intentions of the question setter through the clues in the problem, which can help us solve the problem.

Take a look at LeetCode problem #931 "Minimum Falling Path Sum". The input is a n * n 2D array matrix. You need to calculate the minimum sum of the path from the first row to the last row:

931. Minimum Falling Path Sum | LeetCode |

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: There are two falling paths with a minimum sum as shown.

Example 2:

Input: matrix = [[-19,57],[-40,-5]]
Output: -59
Explanation: The falling path with a minimum sum is shown.

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

The function signature is as follows:

int minFallingPathSum(int[][] matrix);

int minFallingPathSum(vector<vector<int>>& matrix);

def minFallingPathSum(matrix: List[List[int]]) -> int

func minFallingPathSum(matrix [][]int) int {}

var minFallingPathSum = function(matrix) {}

Today's problem is not particularly difficult, so I'll use it to explain how to determine the return values for the base case, the initial values for the memoization, and the return values for index out-of-bounds situations.

However, I will still follow the Standard Approach to Dynamic Programming to discuss the solution strategy for this problem.

Solution Strategy

First, we can define a dp array: