对自己好一点，心情不好的时候，什么都别考虑，去吃自己爱吃的吧。
LC每日一题，参考931. 下降路径最小和。
题目
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 **的 最小和 。
下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13
解释：如图所示，为和最小的两条下降路径
解题思路
- 记忆化搜索：最容易想到的就是以第一行每个元素开始递归往下找三个分支,每个分支继续递归找三个分支直到最后一行,然后使用记忆化搜索减少重复计算。
- 动态规划：也可反向思考,定义动态规划方程,每行每个元素都有对应的当前最小路径,计算所有最小路径,最后一行的所有最小路径的最小值即为结果。
记忆化搜索
不使用记忆化搜索时间复杂度O(3^n)会超时.
class Solution {
int[][] memo;
public int minFallingPathSum(int[][] matrix) {
//枚举每一行 下一行从三个数里面找值最小的
int n = matrix.length, ans = Integer.MAX_VALUE;
//记忆化搜索
memo = new int[n][n];
for(int i = 0; i < n; i++) Arrays.fill(memo[i],Integer.MAX_VALUE);
for(int i = 0; i < n; i++) {
ans = Math.min(ans,dfs(matrix,0,i));
}
return ans;
}
int dfs(int[][] matrix,int row,int col) {
int n = matrix.length, res = Integer.MAX_VALUE;
if(row == n) return 0;
if(memo[row][col] != Integer.MAX_VALUE) return memo[row][col];
if(col-1 >= 0) res = Math.min(res,dfs(matrix,row+1,col-1));
res = Math.min(res,dfs(matrix,row+1,col));
if(col+1 < n) res = Math.min(res,dfs(matrix,row+1,col+1));
return memo[row][col] = matrix[row][col] + res;
}
}
复杂度分析
- 时间复杂度：
O(n^2)，n为矩阵行/列数,记忆化搜索搜索状态个数n^2,单个状态只会计算一次。 - 空间复杂度：
O(n^2)，记忆数组空间n^2。
动态规划
对于第二行每个元素的最小路径和与正上一行正上方三个元素有关,其他行同理.
class Solution {
public int minFallingPathSum(int[][] matrix) {
int n = matrix.length,ans = Integer.MAX_VALUE;
//动态规划dp[i][j] 表示到达i,j坐标时的最小路径和
int[][] dp = new int[n][n];
//转移方程
for(int i = 0; i < n; i++) dp[0][i] = matrix[0][i];
for(int i = 1; i < n; i++) {
for(int j = 0; j < n; j++) {
//从正上方三个元素选最小
int res = dp[i-1][j];
if(j > 0) res = Math.min(res,dp[i-1][j-1]);
if(j+1 < n) res = Math.min(res,dp[i-1][j+1]);
dp[i][j] = res + matrix[i][j];
}
}
for(int i = 0; i < n; i++) ans = Math.min(ans,dp[n-1][i]);
return ans;
}
}
复杂度分析
- 时间复杂度：
O(n^2)，双重循环遍历。 - 空间复杂度：
O(n^2)，动态规划记忆数组空间n^2。
网友评论