成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

[Algo] Longest Descending Path 滑雪問題

ybak / 3425人閱讀

摘要：代碼一個(gè)全局矩陣記錄每個(gè)點(diǎn)能開始的最長路徑對(duì)每個(gè)點(diǎn)開始深度優(yōu)先搜索看是否有必要更新全局最大長度如果已經(jīng)計(jì)算過，則直接返回遞歸上下左右

Longest Descending Path 
給出一個(gè)矩陣，求矩陣中從某個(gè)點(diǎn)開始，最長的下降路徑。路徑可以走上下左右四個(gè)方向。求最長路徑的長度。


1 2 3 4
5 6 7 8



其中一條最長路徑是8 7 6 5 1
記憶化搜索 復(fù)雜度

時(shí)間 O(N) 空間 O(1)

思路

最簡單的方法就是對(duì)每個(gè)點(diǎn)都向四個(gè)方向進(jìn)行深度優(yōu)先搜索，找到最長的下降路徑。然而我們可以用動(dòng)態(tài)規(guī)劃的方法，減少一些重復(fù)計(jì)算，如果我們已經(jīng)算出從點(diǎn)(i, j)開始的最長路徑，則不用再計(jì)算一遍，所以在深度優(yōu)先搜索中，要遞歸的記錄下路徑上這些點(diǎn)的長度：也就是以這些點(diǎn)為起點(diǎn)，能達(dá)到的最長路徑長度。

代碼 
public class Ski {
    // 一個(gè)全局矩陣記錄每個(gè)點(diǎn)能開始的最長路徑
    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++){
                // 對(duì)每個(gè)點(diǎn)開始深度優(yōu)先搜索
                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){
        // 如果已經(jīng)計(jì)算過，則直接返回
        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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/64708.html

相關(guān)文章

  • surprise庫文檔翻譯

    摘要：默認(rèn)值為返回值，一個(gè)對(duì)象，包含了原生用戶原生項(xiàng)目真實(shí)評(píng)分預(yù)測(cè)評(píng)分可能對(duì)后面預(yù)測(cè)有用的一些其他的詳細(xì)信息在給定的測(cè)試集上測(cè)試算法，即估計(jì)給定測(cè)試集中的所有評(píng)分。 這里的格式并沒有做過多的處理，可參考于OneNote筆記鏈接 由于OneNote取消了單頁分享，如果需要請(qǐng)留下郵箱，我會(huì)郵件發(fā)送pdf版本，后續(xù)再解決這個(gè)問題 推薦算法庫surprise安裝 pip install surp...

    JessYanCoding 評(píng)論0 收藏0

  • Tornado 簡單入門教程（二）——Demo2

    摘要：接下來判斷是否為空。因此接下來執(zhí)行。這個(gè)方法用于獲取字典中指定鍵名的鍵值第一個(gè)參數(shù)，如果該鍵名不存在，則返回第二個(gè)參數(shù)設(shè)定的默認(rèn)值。當(dāng)我們填寫好表單，點(diǎn)擊發(fā)布按鈕，表單就以方式被提交到相對(duì)路徑，對(duì)應(yīng)的絕對(duì)路徑為。 前面的話 在Demo1里面,我們練習(xí)了如何部署應(yīng)用、tornado框架的基本結(jié)構(gòu)以及應(yīng)用如何處理請(qǐng)求。 其實(shí)Demo1算不上一個(gè)博客啦。一個(gè)最基本的信息系統(tǒng)一定要包含對(duì)數(shù)據(jù)...

    QLQ 評(píng)論0 收藏0

  • Tornado 簡單入門教程（二）——Demo2

    摘要：接下來判斷是否為空。因此接下來執(zhí)行。這個(gè)方法用于獲取字典中指定鍵名的鍵值第一個(gè)參數(shù)，如果該鍵名不存在，則返回第二個(gè)參數(shù)設(shè)定的默認(rèn)值。當(dāng)我們填寫好表單，點(diǎn)擊發(fā)布按鈕，表單就以方式被提交到相對(duì)路徑，對(duì)應(yīng)的絕對(duì)路徑為。 前面的話 在Demo1里面,我們練習(xí)了如何部署應(yīng)用、tornado框架的基本結(jié)構(gòu)以及應(yīng)用如何處理請(qǐng)求。 其實(shí)Demo1算不上一個(gè)博客啦。一個(gè)最基本的信息系統(tǒng)一定要包含對(duì)數(shù)據(jù)...

    junfeng777 評(píng)論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 評(píng)論0 收藏0

  • [Leetcode] Binary Tree Longest Consecutive Sequenc

    摘要：遞歸法復(fù)雜度時(shí)間空間思路因?yàn)橐易铋L的連續(xù)路徑，我們?cè)诒闅v樹的時(shí)候需要兩個(gè)信息，一是目前連起來的路徑有多長，二是目前路徑的上一個(gè)節(jié)點(diǎn)的值。代碼判斷當(dāng)前是否連續(xù)返回當(dāng)前長度，左子樹長度，和右子樹長度中較大的那個(gè) Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...

    xi4oh4o 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<