当前位置：首页 > article >正文

力扣动态规划-18【算法学习day.112】

article 2025/2/3 14:35:01

前言

###我做这类文章一个重要的目的还是记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.下降路径最小和

题目链接:931. 下降路径最小和 - 力扣（LeetCode）

题面:

代码:

class Solution {
    int[][] matrix;
    int n,m;
    int[][] f;
    int min = Integer.MAX_VALUE;
    public int minFallingPathSum(int[][] matrix) {
        this.matrix = matrix;
        n = matrix.length;
        m = matrix[0].length;
        f = new int[n][m];
        for(int[] arr:f){
            Arrays.fill(arr,-10000000);
        }
        for(int i = 0;i<m;i++){
            int flag = recursion(n-1,i);
            min = Math.min(min,flag);  
        }
        return min;
    }
    public int recursion(int x,int y){
        if(x==0&&y>=0){
            return matrix[x][y];
        }
        if(x<0||y<0)return 0;
        if(f[x][y]!=-10000000)return f[x][y];
        int a=Integer.MAX_VALUE;
        int b=Integer.MAX_VALUE;
        int c=Integer.MAX_VALUE;

        if(x-1>=0&&y+1<m){
            a = recursion(x-1,y+1);
        }
        if(x-1>=0&&y-1>=0){
            b = recursion(x-1,y-1);
        }
        c = recursion(x-1,y);
        return f[x][y] = Math.min(Math.min(a,b),c)+matrix[x][y];
    }
}