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

前言

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

---

习题

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];}
}

---

 后言

上面是动态规划相关的习题，共勉