base case 和备忘录的初始值怎么定？

931. 下降路径最小和 https://leetcode.cn/problems/minimum-falling-path-sum

931. Minimum Falling Path Sum https://leetcode.com/problems/minimum-falling-path-sum

Info

已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	Difficulty
931. Minimum Falling Path Sum	🟠

Prerequisites

Before reading this article, you should first learn:

• Dynamic Programming Core Framework

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:

java 🟢

int minFallingPathSum(int[][] matrix);

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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:

java 🟢

int dp(int[][] matrix, int i, int j);

cpp 🤖

int dp(vector<vector<int>>& matrix, int i, int j);

python 🤖

def dp(matrix: List[List[int]], i: int, j: int) -> int:

go 🤖

func dp(matrix [][]int, i int, j int) int

javascript 🤖

var dp = function(matrix, i, j){
    // code goes here
}

The meaning of this dp function is as follows:

Starting from the first row (matrix[0][..]) and falling down, the minimum path sum to reach the position matrix[i][j] is dp(matrix, i, j).

Based on this definition, we can write the logic for the main function:

java 🟢

int minFallingPathSum(int[][] matrix) {
    int n = matrix.length;
    int res = Integer.MAX_VALUE;

    // the endpoint could be any column in the last row
    for (int j = 0; j < n; j++) {
        res = Math.min(res, dp(matrix, n - 1, j));
    }

    return res;
}

cpp 🤖

int minFallingPathSum(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int res = INT_MAX;

    // the endpoint could be any column in the last row
    for (int j = 0; j < n; j++) {
        res = min(res, dp(matrix, n - 1, j));
    }

    return res;
}

python 🤖

def minFallingPathSum(matrix: List[List[int]]) -> int:
    n = len(matrix)
    res = float("inf")
    
    # the endpoint could be any column in the last row
    for j in range(n):
        res = min(res, dp(matrix, n - 1, j))
    
    return res

go 🤖

func minFallingPathSum(matrix [][]int) int {
    n := len(matrix)
    res := math.MaxInt32

    // the endpoint could be any column in the last row
    for j := 0; j < n; j++ {
        res = min(res, dp(matrix, n - 1, j))
    }

    return res
}

javascript 🤖

var minFallingPathSum = function(matrix) {
    var n = matrix.length;
    var res = Number.MAX_VALUE;

    // the destination could be any column in the last row
    for (var j = 0; j < n; j++) {
        res = Math.min(res, dp(matrix, n - 1, j));
    }

    return res;
};

Because we could end up in any column of the last row, we need to explore all possibilities to find the column that results in the minimum path sum.

Next, let's see how the dp function is implemented.

For matrix[i][j], it can only be reached from matrix[i-1][j], matrix[i-1][j-1], or matrix[i-1][j+1].

So, if we know the minimum path sums to reach the positions (i-1, j), (i-1, j-1), and (i-1, j+1), and add the value of matrix[i][j], we can calculate the minimum path sum to reach the position (i, j):

java 🟢

int dp(int[][] matrix, int i, int j) {
    // illegal index check
    if (i < 0 || j < 0 ||
        i >= matrix.length ||
        j >= matrix[0].length) {
        // return a special value
        return 99999;
    }
    // base case
    if (i == 0) {
        return matrix[i][j];
    }
    // state transition
    return matrix[i][j] + min(

            dp(matrix, i - 1, j), 
            dp(matrix, i - 1, j - 1),
            dp(matrix, i - 1, j + 1)
        );
}

int min(int a, int b, int c) {
    return Math.min(a, Math.min(b, c));
}

cpp 🤖

int dp(vector<vector<int>>& matrix, int i, int j) {
    // illegal index check
    if (i < 0 || j < 0 ||
        i >= matrix.size() ||
        j >= matrix[0].size()) {
        // return a special value
        return 99999;
    }
    // base case
    if (i == 0) {
        return matrix[i][j];
    }
    // state transition
    return matrix[i][j] + min({

            dp(matrix, i - 1, j), 
            dp(matrix, i - 1, j - 1),
            dp(matrix, i - 1, j + 1)
        });
}

python 🤖

def dp(matrix: List[List[int]], i: int, j: int) -> int:
    # illegal index check
    if i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0]):
        # return a special value
        return 99999
    # base case
    if i == 0:
        return matrix[i][j]
    # state transition
    return matrix[i][j] + min( 

            dp(matrix, i - 1, j), 
            dp(matrix, i - 1, j - 1), 
            dp(matrix, i - 1, j + 1)
        )

go 🤖

func dp(matrix [][]int, i int, j int) int {
    // illegal index check
    if i < 0 || j < 0 ||
        i >= len(matrix) || j >= len(matrix[0]) {
        // return a special value
        return 99999
    }
    // base case
    if i == 0 {
        return matrix[i][j]
    }
    // state transition
    return matrix[i][j] + min(

        dp(matrix, i-1, j),
        dp(matrix, i-1, j-1),
        dp(matrix, i-1, j+1),
    )
}

func min(a int, b int, c int) int {
    if a < b {
        if a < c {
            return a
        } else {
            return c
        }
    } else if b < c {
        return b
    } else {
        return c
    }
}

javascript 🤖

var dp = function(matrix, i, j) {
    // illegal index check
    if (i < 0 || j < 0 ||
        i >= matrix.length ||
        j >= matrix[0].length) {
        // return a special value
        return 99999;
    }
    // base case
    if (i == 0) {
        return matrix[i][j];
    }
    // state transition
    return matrix[i][j] + min(

            dp(matrix, i - 1, j), 
            dp(matrix, i - 1, j - 1),
            dp(matrix, i - 1, j + 1)
        );
}

var min = function(a, b, c) {
    return Math.min(a, Math.min(b, c));
}

Of course, the above code is a brute-force solution. We can use memoization to eliminate overlapping subproblems. The complete code is as follows:

java 🟢

class Solution {
    // memoization
    int[][] memo;

    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int res = Integer.MAX_VALUE;
        // initialize the values in the memoization array to 66666
        memo = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(memo[i], 66666);
        }
        // the endpoint could be any column in matrix[n-1]
        for (int j = 0; j < n; j++) {
            res = Math.min(res, dp(matrix, n - 1, j));
        }
        return res;
    }

    int dp(int[][] matrix, int i, int j) {
        // 1. index validity check
        if (i < 0 || j < 0 ||
            i >= matrix.length ||
            j >= matrix[0].length) {
            
            return 99999;
        }
        // 2、base case
        if (i == 0) {
            return matrix[0][j];
        }
        // 3. check the memoization array to prevent repeated calculations
        if (memo[i][j] != 66666) {
            return memo[i][j];
        }
        // perform state transition
        memo[i][j] = matrix[i][j] + min(
                dp(matrix, i - 1, j), 
                dp(matrix, i - 1, j - 1),
                dp(matrix, i - 1, j + 1)
            );

        return memo[i][j];
    }

    int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }
}

cpp 🤖

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        int n = matrix.size();
        int res = INT_MAX;
        // Initialize the values in the memo to 66666
        memo = vector<vector<int>>(n, vector<int>(n, 66666));
        // The endpoint may be in any column of matrix[n-1]
        for (int j = 0; j < n; j++) {
            res = min(res, dp(matrix, n - 1, j));
        }
        return res;
    }

private:
    // Memoization table
    vector<vector<int>> memo;

    int dp(vector<vector<int>>& matrix, int i, int j) {
        // 1. Check the validity of the index
        if (i < 0 || j < 0 || i >= matrix.size() || j >= matrix[0].size()) {
            return 99999;
        }
        // 2、base case
        if (i == 0) {
            return matrix[0][j];
        }
        // 3. Check the memoization table to prevent redundant calculations
        if (memo[i][j] != 66666) {
            return memo[i][j];
        }
        // Perform state transition
        memo[i][j] = matrix[i][j] + min3(
            dp(matrix, i - 1, j), 
            dp(matrix, i - 1, j - 1), 
            dp(matrix, i - 1, j + 1)
        );

        return memo[i][j];
    }

    int min3(int a, int b, int c) {
        return std::min(a, std::min(b, c));
    }
};

python 🤖

class Solution:
    def __init__(self):
        self.memo = []

    def minFallingPathSum(self, matrix):
        n = len(matrix)
        res = float('inf')
        # Initialize the values in the memo to 66666
        self.memo = [[66666] * n for _ in range(n)]
        
        # The endpoint could be any column in matrix[n-1]
        for j in range(n):
            res = min(res, self.dp(matrix, n - 1, j))
        
        return res

    def dp(self, matrix, i, j):
        # 1. Check the validity of the index
        if i < 0 or j < 0 or i >= len(matrix) or j >= len(matrix[0]):
            return 99999
        
        # 2、base case
        if i == 0:
            return matrix[0][j]
        
        # 3. Check the memo to prevent redundant calculations
        if self.memo[i][j] != 66666:
            return self.memo[i][j]
        
        # Perform state transition
        self.memo[i][j] = matrix[i][j] + min(
            self.dp(matrix, i - 1, j), 
            self.dp(matrix, i - 1, j - 1),
            self.dp(matrix, i - 1, j + 1)
        )
        return self.memo[i][j]

go 🤖

import (
	"fmt"
	"math"
)

func minFallingPathSum(matrix [][]int) int {
	n := len(matrix)
	res := math.MaxInt32
	
	// initialize the values in the memo to 66666
	memo := make([][]int, n)
	for i := range memo {
		memo[i] = make([]int, n)
		for j := range memo[i] {
			memo[i][j] = 66666
		}
	}
	
	// define the dp function
	var dp func(matrix [][]int, i, j int) int
	dp = func(matrix [][]int, i, j int) int {
		// 1. index validity check
		if i < 0 || j < 0 || i >= len(matrix) || j >= len(matrix[0]) {
			return 99999
		}
		// 2、base case
		if i == 0 {
			return matrix[0][j]
		}
		// 3. check the memo to prevent redundant calculations
		if memo[i][j] != 66666 {
			return memo[i][j]
		}
		// perform state transition
		memo[i][j] = matrix[i][j] + min(
			dp(matrix, i-1, j), 
			dp(matrix, i-1, j-1), 
			dp(matrix, i-1, j+1),
		)
		return memo[i][j]
	}

	// the endpoint may be in any column of matrix[n-1]
	for j := 0; j < n; j++ {
		colSum := dp(matrix, n-1, j)
        if colSum < res {
            res = colSum
        }
	}
	return res
}

func min(a, b, c int) int {
	if a < b && a < c {
		return a
	} else if b < c {
		return b
	}
	return c
}

javascript 🤖

var minFallingPathSum = function(matrix) {
    let n = matrix.length;
    let res = Number.MAX_VALUE;
    // Initialize the values in the memo to 66666
    let memo = Array.from({ length: n }, () => Array(n).fill(66666));
    
    // The endpoint may be in any column of matrix[n-1]
    for (let j = 0; j < n; j++) {
        res = Math.min(res, dp(matrix, n - 1, j, memo));
    }
    return res;
};

// Auxiliary function
var dp = function(matrix, i, j, memo) {
    // 1. Check the validity of the index
    if (i < 0 || j < 0 || i >= matrix.length || j >= matrix[0].length) {
        return 99999;
    }
    // 2、base case
    if (i == 0) {
        return matrix[0][j];
    }
    // 3. Check the memo to prevent repeated calculations
    if (memo[i][j] != 66666) {
        return memo[i][j];
    }

    // Perform state transition
    memo[i][j] = matrix[i][j] + min(
        dp(matrix, i - 1, j, memo), 
        dp(matrix, i - 1, j - 1, memo),
        dp(matrix, i - 1, j + 1, memo)
    );

    return memo[i][j];
};

var min = function(a, b, c) {
    return Math.min(a, Math.min(b, c));
};

If you've read other articles on dynamic programming, this problem-solving approach should be quite easy to understand.

In this article, we will delve into three questions about the dp function:

1. For index validity checks, why is the return value 99999? Would other values work?

2. Why is the base case i == 0?

3. Why is the initial value of the memoization table memo set to 66666? Would other values work?

How to Determine the Base Case Condition?

First, let's discuss why the base case is i == 0 and why the return value is matrix[0][j]. This is determined by the definition of the dp function.

Recall our dp function definition:

Starting from the first row (matrix[0][..]), the minimum path sum to fall to the position matrix[i][j] is dp(matrix, i, j).

According to this definition, we start falling from matrix[0][j]. So, if our destination is i == 0, the required path sum is naturally matrix[0][j].

How to Determine the Initial Values for the Memoization Array?

Let's discuss why the initial value for the memoization array memo is set to 66666. This is determined by the data range provided in the problem.

What is the purpose of the memo array?

It prevents redundant calculations by storing the results of dp(matrix, i, j) in memo[i][j]. When encountering a repeated calculation, it can return the stored result directly.

Therefore, we need to know whether memo[i][j] has stored a result, right? If it has, we return the result directly; if not, we perform the recursive calculation.

So, the initial value of memo must be a special value that is distinct from any valid answer.

Let's revisit the data range provided in the problem:

The matrix is an n x n 2D array where 1 <= n <= 100. For the elements in the 2D array, -100 <= matrix[i][j] <= 100.

Assume the size of matrix is 100 x 100, and all elements are 100. The sum of the path from the first row would be 100 x 100 = 10000, which is the maximum valid answer.

Similarly, if the matrix size is 100 x 100 and all elements are -100, the path sum from the first row would be -100 x 100 = -10000, which is the minimum valid answer.

This means the valid results for this problem fall within the range [-10000, 10000].

Therefore, the initial value for memo should be outside the range [-10000, 10000]. In other words, any value in the range (-inf, -10001] U [10001, +inf) is acceptable.

How to Determine the Return Value for Boundary Cases?

Finally, let's discuss how to determine the return value for invalid indices. This depends on the logic of our state transition equation.

For this problem, the basic logic of the state transition is as follows:

int dp(int[][] matrix, int i, int j) {

    return matrix[i][j] + min(
            dp(matrix, i - 1, j), 
            dp(matrix, i - 1, j - 1),
            dp(matrix, i - 1, j + 1)
        );
}

Clearly, operations like i - 1, j - 1, j + 1 can cause index out-of-bounds errors. For the dp function when encountering such indices, it should return a value that can never be reached.

Since we are using the min function, the final returned value is the minimum. Therefore, for invalid indices, as long as the dp function returns a maximum value that will never be used, it's fine.

As mentioned earlier, the valid answer range is [-10000, 10000]. So, any return value greater than 10000 acts as an unreachable maximum value.

In other words, returning any value from the interval [10001, +inf) ensures it won't be picked.

With this, we have illustrated three detailed issues related to dynamic programming.

As an extension, I recommend that when solving problems, besides understanding the problem itself, never overlook other information provided in the question.

The example in this article shows how the range of test case data helps determine "what constitutes a special value," aiding in translating thoughts into code.

Moreover, data ranges can help estimate the time/space complexity of algorithms.

For instance, if you only think of a brute-force solution for an algorithmic problem with high time complexity, and the given data size is large, it indicates that the solution might be flawed or has room for optimization.

Besides data ranges, sometimes problems also specify the required time complexity of the algorithm, which hints at certain approaches.

For example, if the required complexity is O(NlogN), how can you achieve a logarithmic complexity?

You would likely need to use binary search or related data structures like TreeMap, PriorityQueue, etc.

Similarly, if a problem requires O(MN) complexity, what comes to mind?

You might guess that the conventional approach is using backtracking for brute-force enumeration, but a better approach could be dynamic programming, specifically a two-dimensional dynamic programming that requires an M * N two-dimensional dp array, leading to such a time complexity.

If you already have a clear plan, then consider this redundant; guesses aren't always accurate. But if you're lacking in ideas, these推测 can at least give you some direction.

In summary, think critically and don't miss any clues. With practice, you'll become a problem-solving pro.

---

引用本文的题目

安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：

LeetCode	力扣
63. Unique Paths II	63. 不同路径 II

---