[Algo] Longest Descending Path 滑雪问题

ybak 发布于2019-08-14 12:47 / 3421人阅读

摘要：代码一个全局矩阵记录每个点能开始的最长路径对每个点开始深度优先搜索看是否有必要更新全局最大长度如果已经计算过，则直接返回递归上下左右

Longest Descending Path

给出一个矩阵，求矩阵中从某个点开始，最长的下降路径。路径可以走上下左右四个方向。求最长路径的长度。

1 2 3 4
5 6 7 8

其中一条最长路径是8 7 6 5 1

记忆化搜索 复杂度

时间 O(N) 空间 O(1)

思路

最简单的方法就是对每个点都向四个方向进行深度优先搜索，找到最长的下降路径。然而我们可以用动态规划的方法，减少一些重复计算，如果我们已经算出从点(i, j)开始的最长路径，则不用再计算一遍，所以在深度优先搜索中，要递归的记录下路径上这些点的长度：也就是以这些点为起点，能达到的最长路径长度。

代码

public class Ski {
    // 一个全局矩阵记录每个点能开始的最长路径
    int[][] dp;
    
    public int getLongestPath(int[][] matrix){
        dp = new int[matrix.length][matrix[0].length];
        int max = 0;
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                // 对每个点开始深度优先搜索
                dp[i][j] = dfs(i, j, matrix);
                // 看是否有必要更新全局最大长度
                if(dp[i][j] > max){
                    max = dp[i][j];
                }
            }
        }
        return max;
    }
    
    public int dfs(int i, int j, int[][] m){
        // 如果已经计算过，则直接返回
        if(dp[i][j] != 0){
            return dp[i][j];
        }
        int length = 1;
        // 递归上下左右
        if(i > 0 && m[i - 1][j] < m[i][j]){
            length = Math.max(dfs(i - 1, j, m) + 1, length);
        }
        if(j > 0 && m[i][j - 1] < m[i][j]){
            length = Math.max(dfs(i, j - 1, m) + 1, length);
        }
        if(i < m.length - 1 && m[i + 1][j] < m[i][j]){
            length = Math.max(dfs(i + 1, j, m) + 1, length);
        }
        if(j < m[0].length - 1 && m[i][j + 1] < m[i][j]){
            length = Math.max(dfs(i, j + 1, m) + 1, length);
        }
        dp[i][j] = length;
        return length;
    }
}

云服务器 GPU云服务器 Descending Algo Longest PATH

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64708.html

surprise库文档翻译

摘要：默认值为返回值，一个对象，包含了原生用户原生项目真实评分预测评分可能对后面预测有用的一些其他的详细信息在给定的测试集上测试算法，即估计给定测试集中的所有评分。这里的格式并没有做过多的处理，可参考于OneNote笔记链接由于OneNote取消了单页分享，如果需要请留下邮箱，我会邮件发送pdf版本，后续再解决这个问题推荐算法库surprise安装 pip install surp...

JessYanCoding 2019-07-31 10:25 评论0 收藏0
Tornado 简单入门教程（二）——Demo2

摘要：接下来判断是否为空。因此接下来执行。这个方法用于获取字典中指定键名的键值第一个参数，如果该键名不存在，则返回第二个参数设定的默认值。当我们填写好表单，点击发布按钮，表单就以方式被提交到相对路径，对应的绝对路径为。前面的话在Demo1里面,我们练习了如何部署应用、tornado框架的基本结构以及应用如何处理请求。其实Demo1算不上一个博客啦。一个最基本的信息系统一定要包含对数据...

QLQ 2019-07-24 17:57 评论0 收藏0
Tornado 简单入门教程（二）——Demo2

摘要：接下来判断是否为空。因此接下来执行。这个方法用于获取字典中指定键名的键值第一个参数，如果该键名不存在，则返回第二个参数设定的默认值。当我们填写好表单，点击发布按钮，表单就以方式被提交到相对路径，对应的绝对路径为。前面的话在Demo1里面,我们练习了如何部署应用、tornado框架的基本结构以及应用如何处理请求。其实Demo1算不上一个博客啦。一个最基本的信息系统一定要包含对数据...

junfeng777 2019-06-26 16:51 评论0 收藏0
[LeetCode] 388. Longest Absolute File Path

Problem Suppose we abstract our file system by a string in the following manner: The string dirntsubdir1ntsubdir2nttfile.ext represents: dir subdir1 subdir2 file.ext The directory dir ...

wawor4827 2019-08-16 13:36 评论0 收藏0
[Leetcode] Binary Tree Longest Consecutive Sequenc

摘要：递归法复杂度时间空间思路因为要找最长的连续路径，我们在遍历树的时候需要两个信息，一是目前连起来的路径有多长，二是目前路径的上一个节点的值。代码判断当前是否连续返回当前长度，左子树长度，和右子树长度中较大的那个 Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...

xi4oh4o 2019-08-14 16:16 评论0 收藏0