题解 | #矩阵最长递增路径#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 递增路径的最大长度
 * @param matrix int整型二维数组 描述矩阵的每个数
 * @return int整型
 */

//方法1：暴力法。m*n个元素 -> m*n个元素；判断每条路径是否递增； -》递增的情况下是否是最长（长度是多少）
//方法2:采用dfs的方法回溯；从每个元素出发；可以抵达的最长路径是啥？长度是？
//方法3:在方法2的层面上进行优化；剔除调那些已经访问过的；不再访问的->动态规划记录当前位置的最优解；然后和当前位置的进行组合

// dfs发现最长的路径
/*
func dfsFindLongestLength(i, j, m, n int, matrix [][]int) int {

	//当前位置；上下左右左移动
	//如果上下左右没有满足的可以移动的位置，返回（出界；没有更大的元素）
	//符合条件才移动
	var (
		maxLength int
	)

	if i-1 >= 0 && matrix[i][j] < matrix[i-1][j] {
		maxLength = dfsFindLongestLength(i-1, j, m, n, matrix)
	}
	if i+1 < m && matrix[i][j] < matrix[i+1][j] {
		tmp := dfsFindLongestLength(i+1, j, m, n, matrix)
		if tmp > maxLength {
			maxLength = tmp
		}
	}
	if j-1 >= 0 && matrix[i][j] < matrix[i][j-1] {
		tmp := dfsFindLongestLength(i, j-1, m, n, matrix)
		if tmp > maxLength {
			maxLength = tmp
		}
	}
	if j+1 < n && matrix[i][j] < matrix[i][j+1] {
		tmp := dfsFindLongestLength(i, j+1, m, n, matrix)
		if tmp > maxLength {
			maxLength = tmp
		}
	}
	return maxLength + 1
}

func solve(matrix [][]int) int {
	// write code here
	//从各个位置出发；最长分别的最长路径是？
	res := 0
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			tmp := dfsFindLongestLength(i, j, len(matrix), len(matrix[0]), matrix)
			if tmp > res {
				res = tmp
			}
		}
	}
	return res
}
*/

//采用动态规划优化之后的解
// dfs发现最长的路径
func dfsFindLongestLength(i, j, m, n int, matrix, curPosLongest [][]int) int {

	//当前位置；上下左右左移动c
	//如果上下左右没有满足的可以移动的位置，返回（出界；没有更大的元素）
	//符合条件才移动
	var (
		maxLength int
		tmp       int
	)

	if i-1 >= 0 && matrix[i][j] < matrix[i-1][j] {
		if curPosLongest[i-1][j] != 0 {
			maxLength = curPosLongest[i-1][j]
		} else {
			maxLength = dfsFindLongestLength(i-1, j, m, n, matrix, curPosLongest)
		}

	}
	if i+1 < m && matrix[i][j] < matrix[i+1][j] {
		if curPosLongest[i+1][j] != 0 {
			tmp = curPosLongest[i+1][j]
		} else {
			tmp = dfsFindLongestLength(i+1, j, m, n, matrix, curPosLongest)
		}
		if tmp > maxLength {
			maxLength = tmp
		}
	}
	if j-1 >= 0 && matrix[i][j] < matrix[i][j-1] {
		if curPosLongest[i][j-1] != 0 {
			tmp = curPosLongest[i][j-1]
		} else {
			tmp = dfsFindLongestLength(i, j-1, m, n, matrix, curPosLongest)
		}
		if tmp > maxLength {
			maxLength = tmp
		}
	}
	if j+1 < n && matrix[i][j] < matrix[i][j+1] {
		if curPosLongest[i][j+1] != 0 {
			tmp = curPosLongest[i][j+1]
		} else {
			tmp = dfsFindLongestLength(i, j+1, m, n, matrix, curPosLongest)
		}
		if tmp > maxLength {
			maxLength = tmp
		}
	}
	curPosLongest[i][j] = maxLength + 1
	return curPosLongest[i][j]
}

func solve(matrix [][]int) int {
	// write code here
	//从各个位置出发；最长分别的最长路径是？
	curPosLongest := make([][]int, len(matrix))
	for i := 0; i < len(matrix); i++ {
		tmp := make([]int, len(matrix[0]))
		curPosLongest[i] = tmp
	}

	res := 0
	for i := 0; i < len(matrix); i++ {
		for j := 0; j < len(matrix[0]); j++ {
			tmp := dfsFindLongestLength(i, j, len(matrix), len(matrix[0]), matrix, curPosLongest)
			if tmp > res {
				res = tmp
			}
		}
	}
	return res
}