# What's the relevance of the numbers not being negative?

• I understand that in some shortest path algorithms on general node weighted graphs, negative cycles lead to non-termination, but here I do not see any problem, so why does the question state that the weights are not negative?

• I guess it's just simplifies the problem and allows for another class of solutions: ones which would fail on negative cycles.

If you don't know or like dynamic programming you can traverse the solution space as a graph and find the shortest path (Dijkstra, A*, etc.).

• There are no cycles, though, since edges only go down or right.

• Hmm, that's right, then it really doesn't make a difference.

Maybe there's some less-known algorithm where `>=0` can be assumed and incorporated.

• Short: because it doesn't matter if there are negative numbers.

Long: Suppose there are negative numbers in the `grid`, if you find the minimum of the whole grid, it must be negative, let's call this `min`. If you take the `grid` and add `-min` to each cell: you get a `grid'` which doesn't have negative numbers anymore. The minimums have been replaced by `min + -min = 0`, everything else is positive. The minimal `path'` you find in `grid'` will have an equivalent (same steps) minimal `path` in `grid` as well and `cost(path) = cost(path') + min*len(path)`.

• Since you debunked this one, rightfully, I had an idea this morning when I woke up, see new answer.

• The "because" made me lol :-)

Good analysis. Subpaths are of course also equally affected, meaning if path A to a certain cell was originally better than path B to that cell, then path A will still be better than path B after adding `-min` everywhere. So solutions will make the same decisions and will find the same optimal path with or without the adding (unless they do something weird :-)

I suspect the author didn't really make the restriction on purpose.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.