題目描述

給定一個包含非負整數的 m x n 網格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。

說明：每次只能向下或者向右移動一步。

示例

力扣最長公共子序列？示例 1：

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因為路徑 1→3→1→1→1 的總和最小。

示例 2：
輸入：grid = [[1,2,3],[4,5,6]]
輸出：12

源代碼

思路：根據題意，每次只能向下走或者向右走，那么換句話說就是，下一位置要么就是從左邊過來的，要么就是從上面過來的，取二者的最小值即可。
找出遞推式：
f[i][j]=min(f[i][j-1],f[i-1][j])+grid[i][j];
然后先列出邊界條件。

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

最小k個數 力扣。復雜度分析：

• 時間復雜度：O(m*n)，其中 m 和 n 分別是網格的行數和列數。需要對整個網格遍歷一次，計算 f 的每個元素的值。

• 空間復雜度：O(m*n)，其中 m 和 n分別是網格的行數和列數。創建一個二維數組 f，和網格大小相同。

力扣是什么？