程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode64:Minimum Path Sum

LeetCode64:Minimum Path Sum

編輯:C++入門知識

LeetCode64:Minimum Path Sum


Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

這道題和前面很多題都好像。


解法一:

轉態A[i][j]可以表示左上點到grid[i][j]作為右下角的路徑的最小和,那麼它只依賴於A[i-1][j]和A[i][j-1]。狀態轉移方程是:
A[i][j]=min{A[i-1][j],A[i][j-1]}+grid[i][j]
需要注意的是邊界條件的處理,但是可以將A[i][j]的維數設置的比grid[i][j]的維數大1,這樣就可以將邊界統一起來了。
時間復雜度是O(M*N),M是矩陣的寬,N是矩陣的高。空間復雜度是O(M*N)。
runtime:28ms

class Solution {
public:
    int minPathSum(vector>& grid) {
        int height=grid.size();
        int width=grid[0].size();
        int current=0;
        vector > mask(height+1,vector(width+1,INT_MAX));
        for(int i=0;i

解法二:

解法一在空間上是可以做優化的,可以將空間復雜度降低為O(min(M,N))。
因為A[i][j]只依賴於A[i-1][j]和A[i][j-1],所以可以只使用一個vector來存儲即可。
下面是按列進行掃描的算法,代碼來自:
https://leetcode.com/discuss/38360/easy-dp-solution-in-c-with-detailed-explanations-o-n-space

int minPathSum(vector>& grid) {
    int m = grid.size();
    int n = grid[0].size();
    vector cur(m, grid[0][0]);
    for (int i = 1; i < m; i++)
        cur[i] = cur[i - 1] + grid[i][0];
    for (int j = 1; j < n; j++) {
        cur[0]  += grid[0][j];
        for (int i = 1; i < m; i++)
            cur[i] = min(cur[i - 1], cur[i]) + grid[i][j];
    }
    return cur[m - 1];
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved