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

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

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

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

931 降落门路最小和(中等)