亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

[Algo] Longest Descending Path 滑雪問題

ybak / 3474人閱讀

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

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


1 2 3 4
5 6 7 8



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

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

思路

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

代碼 
public class Ski {
    // 一個(gè)全局矩陣記錄每個(gè)點(diǎn)能開始的最長(zhǎng)路徑
    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);
                // 看是否有必要更新全局最大長(zhǎng)度
                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://www.ezyhdfw.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 簡(jiǎn)單入門教程（二）——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 簡(jiǎn)單入門教程（二）——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(zhǎng)的連續(xù)路徑，我們?cè)诒闅v樹的時(shí)候需要兩個(gè)信息，一是目前連起來的路徑有多長(zhǎng)，二是目前路徑的上一個(gè)節(jié)點(diǎn)的值。代碼判斷當(dāng)前是否連續(xù)返回當(dāng)前長(zhǎng)度，左子樹長(zhǎng)度，和右子樹長(zhǎ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)論

閱讀需要支付1元查看
<