关于java:动态规划学习2base-case和备忘录的初始值

持续跟着东哥学习算法，记录一下我的学习过程

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 case
if(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 case
if(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));
}

对于不非法的索引,返回值应该如何确定，这须要咱们依据状态转移方程的逻辑确定