算法 矩阵最长递增路径-(递归回溯+动态规划)

这篇具有很好参考价值的文章主要介绍了算法 矩阵最长递增路径-(递归回溯+动态规划)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

牛客网: BM61

求矩阵的最长递增路径

解题思路:

1. 遍历二维矩阵每个位置,max求出所有位置分别为终点时的最长路径
2. 求某个位置为终点的最长路径时,使用动态规划dp对已经计算出的位置进行记录
3. 处理某个位置的最长路径时,如果dp[i][j]位置已有值,则直接返回即可,否则对此位置赋值1,再对上下左右4个方向进行递归求解,每次递归后返回的最长路径需+1才是当前位置的最长路径,使用max选择最大值赋予dp[i][j],4个方向均遍历完后返回dp[i][j]给主程序。

代码:文章来源地址https://www.toymoban.com/news/detail-730617.html

// go

package 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] = 1
    for 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 here
    if 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 := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            res = max(res, process(matrix, dp, i, j, m, n))
        }
    }
    return res
}

到了这里,关于算法 矩阵最长递增路径-(递归回溯+动态规划)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • BM61 矩阵最长递增路径

    给定一个 n 行 m 列矩阵 matrix ,矩阵内所有数均为非负整数。 你需要在矩阵中找到一条最长路径,使这条路径上的元素是递增的。并输出这条最长路径的长度。 这个路径必须满足以下条件: 1. 对于每个单元格,你可以往上,下,左,右四个方向移动。 你不能在对角线方向上

    2024年02月03日
    浏览(39)
  • 算法思想—枚举、递推、迭代、递归、分治、贪心、动态规划、回溯、模拟、分支定界

    算法思想 枚举(暴力算法) 枚举算法(暴力算法)是一种通过逐一尝试所有可能解来解决问题的算法。它的基本思想是将问题的所有可能答案一一列举出来,并根据一定的判断条件来确定哪些答案是合适的。这种算法通常使用循环来实现,因为需要尝试所有可能的情况。两

    2024年02月01日
    浏览(39)
  • Java中常用算法及示例-分治、迭代、递归、递推、动态规划、回溯、穷举、贪心

    1、分治算法的基本思想是将一个计算复杂的问题分成规模较小、计算简单的小问题求解, 然后综合各个小问题,得到最终答案。 2、穷举(又称枚举)算法的基本思想是从所有可能的情况中搜索正确的答案。 3、迭代法(Iterative Method) 无法使用公式一次求解,而需要使用重复结构

    2024年02月08日
    浏览(45)
  • 算法分析与设计考前冲刺 (算法基础、数据结构与STL、递归和分治、 动态规划、贪心算法、 回溯算法)

    算法分析与设计考前冲刺 算法基础 算法是一系列解决问题的清晰指令,代表着用系统的方法描述解决问题的策略机制。 程序是算法用某种程序设计语言的具体的 具体实现 算法特征: 有穷性(有限步) 确定性 输入 输出 可行性(有限时间) 算法的复杂性: 时间复杂性 和空间复

    2024年02月02日
    浏览(44)
  • 【课设】java:迷宫小游戏(递归与分治、动态规划、贪心算法、回溯法、分支限界法)

    鱼弦:CSDN内容合伙人、CSDN新星导师、全栈领域优质创作者 、51CTO(Top红人+专家博主) 、github开源爱好者(go-zero源码二次开发、游戏后端架构 https://github.com/Peakchen) 递归与分治算法 原理: 递归与分治算法将问题分解为子问题,递归地解决每个子问题,最后将结果合并得到整

    2024年02月02日
    浏览(39)
  • 动态规划之最长递增子序列

    leetcode 300 最长递增子序列 1.定义dp数组:dp[i]表示以nums[i]结尾的最长递增子序列的长度。 2.定义递推公式 dp[i] = max(dp[j] + 1, dp[i]) 因为dp[j] + 1中的dp[j]并非是在前一个已经加1的dp[j]的基础之上再加上1。若从初始状态加1,而dp[i]永远保持的是最大的状态,则dp[j] + 1肯定要小一些。

    2024年01月23日
    浏览(46)
  • leetcode329. 矩阵中的最长递增路径(java)

    来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/longest-increasing-path-in-a-matrix 给定一个 m x n 整数矩阵 matrix ,找出其中 最长递增路径 的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外(即不允许环绕)。 示

    2024年02月10日
    浏览(34)
  • 力扣--动态规划300.最长递增子序列

    一开始想到的方法非常低效,但好理解。   思路分析: 使用二维数组 dp 来记录递增子序列的长度信息,其中 dp[i][0] 表示以 nums[i] 结尾的最长递增子序列的长度, dp[i][1] 表示包含 nums[i] 的最长递增子序列的长度。 初始化 dp 数组,将以第一个元素结尾的递增子序列长度置为

    2024年01月24日
    浏览(50)
  • 【动态规划】求最长递增子序列问题

    最长递增子序列(Longest Increasing Subsequence, LIS ) 子序列:对于任意序列s,它的子序列是通过删除其中零个或多个元素得到的另⼀个序列 注:剩余元素的相对顺序保持不变 给定n个整数组成的序列 s [ 1... n ] s[1...n] s [ 1... n ] ,求最长递增子序列LIS(的长度) 8 3 6 1 3 5 4 7 假设

    2024年02月03日
    浏览(50)
  • LeetCode | C++ 动态规划——300.最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组

    300题目链接 dp 数组定义 dp[i] 表示 i 之前包括 i 的以 nums[i]结尾 的最长递增子序列的长度 需要包含nums[i]结尾,不然在做递增比较的时候,就没有意义了。 递推公式 位置 i 的最长递增子序列 等于 j 从 0 到 i - 1各个位置的最长递增子序列 + 1 的 最大值 if (nums[i] nums[j]) dp[i] = ma

    2024年02月16日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包