企业网站用什么数据库,论坛创建,网站功能配置,长春有微信网站一起整的吗牛客网: BM61
求矩阵的最长递增路径
解题思路:
1. 遍历二维矩阵每个位置#xff0c;max求出所有位置分别为终点时的最长路径 2. 求某个位置为终点的最长路径时#xff0c;使用动态规划dp对已经计算出的位置进行记录 3. 处理某个位置的最长路径时#xff0c;如果dp[i][j]位…牛客网: BM61
求矩阵的最长递增路径
解题思路:
1. 遍历二维矩阵每个位置max求出所有位置分别为终点时的最长路径 2. 求某个位置为终点的最长路径时使用动态规划dp对已经计算出的位置进行记录 3. 处理某个位置的最长路径时如果dp[i][j]位置已有值则直接返回即可否则对此位置赋值1再对上下左右4个方向进行递归求解每次递归后返回的最长路径需1才是当前位置的最长路径使用max选择最大值赋予dp[i][j]4个方向均遍历完后返回dp[i][j]给主程序。
代码:
// gopackage main
// import fmt/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** 递增路径的最大长度* param matrix int整型二维数组 描述矩阵的每个数* return int整型
*/
func max(x, y int) int {if x y {return x} else {return y}
}
var dirs [][]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}func process(matrix, dp [][]int, i, j, m, n int) int {if dp[i][j] 0 {return dp[i][j]}dp[i][j] 1for k : 0; k 4; k {nexti : i dirs[k][0]nextj : j dirs[k][1]if nexti 0 nexti m nextj 0 nextj n matrix[nexti][nextj] matrix[i][j] {dp[i][j] max(dp[i][j], process(matrix, dp, nexti, nextj, m, n) 1)}}return dp[i][j]
}func solve( matrix [][]int ) int {// write code hereif len(matrix) 0 || len(matrix[0]) 0 {return 0}m : len(matrix)n : len(matrix[0])dp : make([][]int, m)for i : 0; i m; i {dp[i] make([]int, n)}res : 0for i : 0; i m; i {for j : 0; j n; j {res max(res, process(matrix, dp, i, j, m, n))}}return res
}
