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

Many readers have questions about the base case and initial values of memoization in dynamic programming problems. This article specifically addresses these issues, while also discussing how to deduce the problem setter’s intentions through subtle clues from the problem statement, aiding us in problem-solving.

Consider LeetCode Problem 931: "Minimum Falling Path Sum", where the input is an n * n 2D array matrix. You are asked to compute 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 problem is from LeetCode 931. Minimum Falling Path Sum.

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 will use it to discuss how to determine the return values of base cases, initial values of memoization, and out-of-bounds index return values.

However, we still need to explain the problem-solving approach according to the Standard Dynamic Programming Routine.

Problem-Solving Approach

First, we can define a dp array: