I am solving some questions on LeetCode. One of the questions is:

> 
> 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.You can only move either down or right at any point in time.
> 
> 
> 

The editorial as well as the solutions posted all use dynamic programming. One of the most upvoted solution is as follows:

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

```

My question is simple: shouldn't this be solved using backtracking? Suppose the input matrix is something like:

> 
> [  
> 
>  [1,2,500]  
> 
>  [100,500,500]  
> 
>  [1,3,4]  
> 
>  ]  
> 
> 
> 
> 

My doubt is because in DP, the solutions to subproblems are a part of the global solution (optimal substructure). However, as can be seen above, when we make a local choice of choosing `2` out of `(2,100)`, we might be wrong, since the future paths might be too expensive (all numbers surrounding 2 are `500`s). So, how is using dynamic programming justified in this case?

To summarize:

1. Shouldn't we use backtracking since we might have to retract our path if we have made an incorrect choice previously (looking at local maxima)?
2. How is this a dynamic programming question?

P.S.: The above solution definitely runs.