路径总和_最小路径总和

以你之姓@ 2023-03-05 08:29 14阅读 0赞

路径总和

**Problem statement:**

**问题陈述：**

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.

给定一个用非负数填充的***mxn***网格，请找到一条从左上到右下的路径，该路径将沿其路径的所有数字的总和最小化。

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

注意：您只能在任何时间点向下或向右移动。

**Input:**

**输入：**

Input starts with an integer ***T*** (≤ 100), denoting the number of test cases. Each case starts with an integer ***m*** and ***n*** (1 ≤ n,m ≤ 1000) denoting the number of rows and number of columns, followed by ***m***rows having n columns as input.

输入以整数***T*** (≤100)开头，表示测试用例的数量。 每种情况都以整数***m***和***n*** (1≤n，m≤1000)开头，表示行数和列数，然后是***m***行，其中n列为输入。

**Output:**

**输出：**

Output the minimum sum to reach the end.

输出最小和以达到末尾。

**Example with explanation:**

**带有说明的示例：**

Input: 
        T = 1
        m = 3, n = 3
        [1,3,1]
        [1,5,1]
        [4,2,1]
    
        Output: 
        7
        Because the path 1→3→1→1→1 minimizes the sum.

**Solution Approach**

**解决方法**

**1) Using dynamic programming**

**1)使用动态编程**

We will create a ***cost\[m\]\[n\]*** matrix for storing the cost of visiting the cell, visiting the ***grid\[0\]\[0\]*** will cost the same, visiting the cell at the first row will only consider the cost of visiting the current cell cost plus the upto the last visited cell that is ***cost\[0\]*****\[j\]=cost\[0\]\[j-1\]+grid\[0\]\[j\],** similarly the cost of visiting the last column will cost the current grid value plus the cost upto the cell before it that it ***cost\[i\]\[0\]=cost\[i-1\]\[0\]+grid\[i\]\[0\]*** and the rest of the cell will cost the min of cost coming from left or cost coming from top that is ***cost\[i\]\[j\]=min(cost\[i\]\[j-1\],cost\[i-1\]\[j\])+grid\[i\]\[j\]***

我们将创建一个***cost \[m\] \[n\]***矩阵来存储访问单元的成本，访问***网格\[0\] \[0\]的***成本相同，访问第一行的单元将仅考虑访问单元的成本。当前单元格成本加上到最近访问的单元格的***成本\[0\]*** **\[j\] = cost \[0\] \[j-1\] + grid \[0\] \[j\]，**类似地，访问最后一列的成本将使当前网格值加上该单元的成本，直到其***cost \[i\] \[0\] = cost \[i-1\] \[0\] + grid \[i\] \[0\]*** ，其余单元将花费最小成本从左开始或从顶部开始的***成本***为***cost \[i\] \[j\] = min(cost \[i\] \[j-1\]，cost \[i-1\] \[j\])+ grid \[i\] \[j\]***

**Pseudo Code:**

**伪代码：**

int findsum(grid[m][n])
    	if(m==0 and n==0)
    		return 0
    	else
    		for(row=0;row<m;row++)
    			for(col=0;col>n;col++)
    				if(row==0 and col==0)
    					cost[row][col]=grid[row][col]
    				if(row==0)
    					cost[row][col]=cost[row][col-1]+grid[row][col]
    				if(col==0)
    					cost[row][col]=cost[row-1][col]+grid[row][col]
    				else
    					cost[row][col]=min(cost[row-1][col],cost[row][col-1])+grid[row][col]

**Time Complexity: O(m\*n)**

**时间复杂度：O(m \* n)**

**C++ Implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    int main()
    {
        
        ll t;
        cout << "Enter number of test case: ";
        cin >> t;
    
        while (t--) {
        
            ll m, n;
    
            cout << "Enter number of rows and columns: ";
            cin >> m >> n;
    
            ll dp[m][n], dp1[m][n];
    
            cout << "Enter elements: ";
            for (ll i = 0; i < m; i++)
                for (ll j = 0; j < n; j++)
                    cin >> dp[i][j];
    
            for (ll i = 0; i < m; i++) {
        
                for (ll j = 0; j < n; j++) {
        
                    if (i == 0 and j == 0)
                        dp1[i][j] = dp[i][j];
                    else if (i == 0 and j != 0)
                        dp1[i][j] = dp1[i][j - 1] + dp[i][j];
                    else if (j == 0 and i != 0)
                        dp1[i][j] = dp1[i - 1][j] + dp[i][j];
                    else
                        dp1[i][j] = min(dp1[i - 1][j], dp1[i][j - 1]) + dp[i][j];
                }
            }
            
            cout << "Minimum Cost: ";
            cout << dp1[m - 1][n - 1] << "\n";
        }
        return 0;
    }

**Output**

**输出量**

Enter number of test case: 2
    Enter number of rows and columns: 3 3
    Enter elements: 1 3 1
    1 5 1
    4 2 1
    Minimum Cost: 7
    Enter number of rows and columns: 4 4
    Enter elements: 1 3 5 2
    3 4 7 2
    4 5 2 8
    4 5 9 1
    Minimum Cost: 22

**2) Using graphical approach**

**2)使用图形方法**

Initially, we will declare the cost of visiting the cell as INFINITE then

最初，我们将访问单元的费用声明为INFINITE，然后

we will use relaxation principal, that is if the cost of visiting the cell plus the distance of the previous cell is smaller than the current cell cost we will update the cost and we keep on doing it until we get the minimum cost.

我们将使用松弛原理，即如果访问单元的成本加上前一个单元的距离小于当前单元的成本，我们将更新该成本，并继续进行直到获得最低成本。

we will use queue with pair to use the index of visited cell or unvisited cell, similar to level order traversal approach.

我们将使用成对队列来使用已访问单元格或未访问单元格的索引，类似于级别顺序遍历方法。

**Pseudo Code:**

**伪代码：**

findsum(grid[m][n])
    	cost[m][n]
    	for(row=0;row<m;row++)
    		for(col=0;col<n;col++)
    			cost[row][col]=INFINTE
    		
    	cost[0][0]=grid[0]][0]
    	queue<pair<int,int>> q
    	q.push({0,0})
    	dx[]={0,1}
    	dy[]={1,0}
    		
    	while(!q.empty())
    	{
    		pair<int,int> p=q.front()
    		q.pop()
    		x=p.first
    		y=p.second
    		for(i=0;i<2;i++)
    		{
    			a=x+dx[i],b=y+dy[i]
    			if(a>=0 and a<m and b>=0 and b<n and cost[a][b]>cost[x][y]+grid[a][b])
    			{
    				q.push({a,b})
    			cost[a][b]=cost[x][y]+grid[a][b]
    			}
    		}
    	}

**Time Complexity: O(n\*m)**

**时间复杂度：O(n \* m)**

**C++ Implementation:**

**C ++实现：**

#include <bits/stdc++.h>
    using namespace std;
    
    typedef long long ll;
    
    int main()
    {
        
        ll t;
        cout << "Enter the number of test cases: ";
        cin >> t;
    
        while (t--) {
        
            cout << "Enter numbe of rows and columns: ";
            ll n, m;
            cin >> n >> m;
    
            ll grid[n][m];
            ll cost[n][m];
    
            cout << "Enter elements: ";
            for (ll i = 0; i < n; i++)
                for (ll j = 0; j < m; j++) {
        
                    cin >> grid[i][j];
                    cost[i][j] = INT_MAX;
                }
    
            cost[0][0] = grid[0][0];
            queue<pair<ll, ll> > q;
            q.push({
         0, 0 });
            ll dx[] = {
         0, 1 };
            ll dy[] = {
         1, 0 };
    
            while (!q.empty()) {
        
                pair<ll, ll> p = q.front();
                q.pop();
                ll x = p.first;
                ll y = p.second;
                for (ll j = 0; j < 2; j++) {
        
                    ll u = x + dx[j];
                    ll v = y + dy[j];
                    if (u >= 0 and u < n and v >= 0 and v < m and cost[u][v] > cost[x][y] + grid[u][v]) {
        
                        cost[u][v] = cost[x][y] + grid[u][v];
                        q.push({
         u, v });
                    }
                }
            }
    
            cout << "Minimum Cost: ";
            cout << cost[n - 1][m - 1] << "\n";
        }
        return 0;
    }

**Output**

**输出量**

Reference: [https://leetcode.com/problems/minimum-path-sum/][https_leetcode.com_problems_minimum-path-sum]

参考： [https][https_leetcode.com_problems_minimum-path-sum] ： [//leetcode.com/problems/minimum-path-sum/][https_leetcode.com_problems_minimum-path-sum]

> 翻译自: [https://www.includehelp.com/icp/minimum-path-sum.aspx][https_www.includehelp.com_icp_minimum-path-sum.aspx]

路径总和

[https_leetcode.com_problems_minimum-path-sum]: https://leetcode.com/problems/minimum-path-sum/
[https_www.includehelp.com_icp_minimum-path-sum.aspx]: https://www.includehelp.com/icp/minimum-path-sum.aspx