maze traversal sum of digits

a grid of NxN is given. each point is assigned a value say num

starting from 1,1 we have to traverse to N,N.

if i,j is current position we can go right or down. How to find the min sum of digits by traversing from 1,1 to n,n along any path any two points can have same number ex

1 2 3

4 5 6

7 8 9

1+2开发者_运维知识库+3+6+9 = 21 n <=10000000000

Output 21 Can someone explain how to approach the problem?

---

This is a dynamic programming problem. The subproblem here is the minimum cost/path to get to any given square. Because you can only move down and to the right, there are only two squares that can let you enter a given square, the one above and the one to the left. Therefore the cost of getting to a square (i,i) is min(cost[i-1][i], cost[i][i-1]) + num. If this would put you out of bounds, only consider the option that is inside the grid. Calculate each row from left to right, doing the top row first and working your way down. The cost you get at (N,N) will be the minimal cost.

---

Here is my solution with dynamic - programming in O(n^2)

you start with (1,1) so you can find say a = (1,2) and b = (2,1) by a = value(1,1) + value(1,2). Then, to find (2,2) select the minimum (a+ value(2,2)) and (b + value(2,2)) and continue with this logic. You can find any minimum sum among (1,1) and (i,j) with that algorithm. Let me explain,

Given Matrix

1 2 3

4 5 6

7 8 9

Shortest path :

1 3 . 
5 . . 
. . . 

so to find (2,2) take the original value(2,2)=5 from Given Matrix and select min(5 + 5), 3 + 5) = 8. so

Shortest path :

1 3 6 
5 8 . 
12 . .

so to find (3,2) select min (12 + 8, 8 + 8) = 16 and (2,3) = min(8 + 6, 6 + 6) = 12

Shortest path :

1 3 6 
5 8 12 
12 16 . 

so the last one (3,3) = min (12 + 9, 16 + 9) = 21

Shortest path :

from (1,1) to any point (i, j)

1 3 6 
5 8 12 
12 16 21

---

You can convert the grid into a graph. The edges get the weights of the values from your grid elements. Then you can find the solution with the shortest path problem.

start--1--+--2--+--3--+
          |     |     |
          4     5     6
          |     |     |
          +--5--+--6--+
          |     |     |
          7     8     9
          |     |     |
          +--8--+--9--end

---

Can someone explain how to approach the problem?

Read about dynamic programming and go from there.

---

Attempt:

Start with the first row and calculate the cumulative values and store them.
Proceed to the second row, now the values could have only come from the left or top (since you can only go left or down), calculate the smallest of the cumulative values for this row.
Iterate down the rows until the last and you'll be able to get the smallest value when you reach the last node.

I claim this algorithm is O(n) since if you use a 2 dimensional array you only need to access all fields at most twice (read from top, left) for read and once for write.

---

If you want to go really fancy or have to operate on massive matrices, A* could also be an option.