溫馨提示×

溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊×
其他方式登錄
點(diǎn)擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

如何分析大數(shù)據(jù)中的最小路徑和

發(fā)布時(shí)間：2021-12-09 10:33:12 來源：億速云 閱讀：96 作者：柒染 欄目：大數(shù)據(jù)

如何分析大數(shù)據(jù)中的最小路徑和，針對(duì)這個(gè)問題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問題的小伙伴找到更簡單易行的方法。

1

 題目描述

給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小，每次移動(dòng)只能向下或者向右一步。

如何分析大數(shù)據(jù)中的最小路徑和

2

 題解

思路：動(dòng)態(tài)規(guī)劃
在LeetCode：最長回文子串中我們介紹了動(dòng)態(tài)規(guī)劃的含義，本次不再贅述，直接進(jìn)入邏輯闡述。

  • 第一步，找到中間狀態(tài)：此處中間狀態(tài)dp[i][j]表示從左上角到達(dá)矩陣中(i，j)元素的最小路徑和。

  • 第二步，確定狀態(tài)轉(zhuǎn)移：根據(jù)路線轉(zhuǎn)移關(guān)系，當(dāng)i=0時(shí)，只能從其左邊到達(dá)，因此dp[i][j]=dp[0][j-1]+grid[i][j]，當(dāng)j=0時(shí)，只能從其上邊到達(dá)，因此dp[i][j]=dp[i-1][0]+grid[i][j]，其他時(shí)候，則有dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]。

class Solution:    def minPathSum(self, grid: List[List[int]]) -> int:               if not grid:            return 0          m = len(grid)        n = len(grid[0])        dp = [ [0] * n for i in range(m)]        for i in range(m):            for j in range(n):                if j == 0 and i == 0:                    dp[i][j] = grid[0][0]                elif j == 0 and i!=0:                    dp[i][j]=dp[i-1][0]+grid[i][j]                elif j!=0 and i==0:                    dp[i][j]=dp[0][j-1]+grid[i][j]                else:                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]        return dp[-1][-1]

關(guān)于如何分析大數(shù)據(jù)中的最小路徑和問題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場，如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手