国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Algo] Longest Descending Path 滑雪問題

ybak / 3416人閱讀

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

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


1 2 3 4
5 6 7 8



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

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

思路

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

代碼 
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++){
                // 對每個點開始深度優(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)計算過，則直接返回
        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)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/64708.html

相關(guān)文章

  • surprise庫文檔翻譯

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

    JessYanCoding 評論0 收藏0

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

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

    QLQ 評論0 收藏0

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

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

    junfeng777 評論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 評論0 收藏0

  • [Leetcode] Binary Tree Longest Consecutive Sequenc

    摘要：遞歸法復(fù)雜度時間空間思路因為要找最長的連續(xù)路徑，我們在遍歷樹的時候需要兩個信息，一是目前連起來的路徑有多長，二是目前路徑的上一個節(jié)點的值。代碼判斷當前是否連續(xù)返回當前長度，左子樹長度，和右子樹長度中較大的那個 Binary Tree Longest Consecutive Sequence Given a binary tree, find the length of the lon...

    xi4oh4o 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<