力扣打卡:931. 下降路径最小和
解题思路
写动态规划,最重要的还是找出当前的状态和子问题状态之间的转移方程
状态转移的方程:一般都是题目中给定的行为或者动作
从题中分析:
找到第一行的最小下降路径和,给定的每一个节点都有三个路径(行为)
每一个节点的最小值都是这三个子问题中的最小值,加上自身的值,这个就是状态转移的过程
定义暴力递归函数的时候
- 定义的函数就是可以求出子问题的结果
- 写暴力递归函数不要想和任何的优化
- 不要乱定义参数,必须要分析出一定结果后再进行编写
- 一定要想着:自定义的函数就是可以得到结果的函数,用自定义的函数得到子问题结果与当前的状态进行连接
- 状态转移方程就是:当前的状态和子问题状态之间的联系
代码
class Solution {
public int minFallingPathSum(int[][] matrix) {
int min = Integer.MAX_VALUE;
int[][] memo = new int[matrix.length][matrix[0].length];
for(int i=0; i<memo.length; i++){
Arrays.fill(memo[i],10001);
}
for(int i=0; i<matrix[0].length; i++){
min = Math.min(min, planB(memo, matrix, 0, i));
}
return min;
}
public int planA(int[][] matrix, int row, int col){
if(col<0 || col>matrix[0].length-1) return Integer.MAX_VALUE;
if(row==matrix.length-1) return matrix[row][col];
int left = planA(matrix, row+1, col-1);
int bottom = planA(matrix, row+1, col);
int right = planA(matrix, row+1, col+1);
return Math.min(left, Math.min(bottom, right)) + matrix[row][col];
}
public int planB(int[][] memo, int[][] matrix, int row, int col){
if(col<0 || col>matrix[0].length-1) return Integer.MAX_VALUE;
if(row==matrix.length-1) return matrix[row][col];
if(memo[row][col] != 10001) return memo[row][col];
int left = planB(memo, matrix, row+1, col-1);
int bottom = planB(memo, matrix, row+1, col);
int right = planB(memo, matrix, row+1, col+1);
memo[row][col] = Math.min(left, Math.min(bottom, right)) + matrix[row][col];
return memo[row][col];
}
}
|