CODEWITHSUNDEEP
algorithmdata-structures
deriavat
deriavat

Reputation: 1

Dynamic programming m*n grid shortest sumpath

I am learning some algos and DS, and came across a DP problem. Looking for some hints. Here is the statement:

Given a mxn 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.

Hints only please!

I've thought of some things but they just don't work. It doesnt make sense because my initial idea was,

Memoize with dp[i][j] where dp[i][j] is the minimum path sum for an i*j grid. This doesn't make sense because I am for example not sure how to get do[i + 1][j + 1] from this.

Is the idea correct. Can you suggest something?

Upvotes: 0

Views: 461

Answers (1)

CodeHunter
CodeHunter

Reputation: 2082

Initialize the corner cells, i.e. dp[0][j] and dp[i][0]. Then for any dp[i][j], the cost of traversing till that path will be val[i][j] + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]).

dp[row][col] should have the cost of minimum path. You can also backtrack using dp[][] and find the minimum cost path as well.

Good luck.

Upvotes: 1

Related Questions