持续跟着东哥学习算法，记录一下我的学习过程
931降落门路最小和(中等)
public int minFallingPathSum(int[][] matrix){ int n=matrix.length; int res=Integer.MAX_VALUE; for(int j=0;j<n;j++){ res=Math.min(res,dp[matrix,n-1,j]); }}这里的j因为咱们的地位是由i,j来独特确定的，之前的先导篇中提到要寻找状态，那么在这道题中的状态就有matrix门路和以及门路的坐标对吧。
//非法索引查看if(i<0||j<0||i>=matrix.length||j>=matrix[0].length){ return 999999;}//base caseif(i==0){ return matrix[i][j];}//状态转移方程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));}这里须要明确的是dp函数和DP Table并不是一个货色*，尽管咱们胜利地结构了dp函数，然而这不代表咱们可能省去[重叠子问题]的计算。
所以，这里应用备忘录的办法来打消重叠子问题
public int minFallingPathSum(int[][] matrix){int n=matrix.length;memo=new int[n][n];for(int i=0;i<n;i++){ Arrays.fill(memo[i],66666);}//起点可能在matrix[n-1]的任意一列for(int j=0;j<n;j++){ res=Math.min(res,dp(matrix,n-1,j));}return res;}//设置备忘录int[][] memo;int dp(int[][] matrix,int i,int j){//1.索引合法性检查if(i<0||j<0||i>=matrix.length||j>=matrix[0].length){ return 99999;}}//2.base caseif(i==0){ reurn matrix[0][j];}//3.查找备忘录if(memo[i][j]!=66666){return memo[i][j];}//4.进行状态转移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));}对于不非法的索引,返回值应该如何确定，这须要咱们依据状态转移方程的逻辑确定