this recurrence wont work..ignore On Mon, Jun 4, 2012 at 8:55 AM, atul anand <[email protected]> wrote:
> 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 <[email protected]> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
