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

Many readers have questions about base cases and initial values of memorization in dynamic programming problems. This article specifically addresses these issues and discusses how to deduce the author's intent from subtle hints in the problem description to aid in problem-solving.

Let's look at LeetCode Problem 931 "Minimum Falling Path Sum", where the input is an n * n two-dimensional array matrix. You are asked to calculate the minimum path sum 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: