find cumulative sum row[0] find cumulative sum of col[0] after this following recurrence will solve the problem.
start from mat[1][1] mat[i][j]=mat[i][j]+min( mat[i][j-1] , mat[i-1][j] ) On Sun, Jun 3, 2012 at 7:30 PM, Decipher <ankurseth...@gmail.com> wrote: > Q) In the 5 by 5 matrix below, the minimal path sum from the top left to > the bottom right, by moving left, right, up, and down, is indicated in bold > red and is equal to 2297. > > > *131* > > 673 > > *234* > > *103* > > *18* > > *201* > > *96* > > *342* > > 965 > > *150* > > 630 > > 803 > > 746 > > *422* > > *111* > > 537 > > 699 > > 497 > > *121* > > 956 > > 805 > > 732 > > 524 > > *37* > > *331* > > > > Write an algorithm to find the same. Also, write an algorithm if the same > matrix contains negative numbers (maybe negative cycle) and compare the > space and time complexity of both. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/3JeyGNqWbs8J. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
