Algorithm {Triangle}

Hey, next problem from leetcode will be Triangle. Task description:

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). Note: Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.

 Stop and think …  

Judging to example we should go level by level and choose smallest “connected” value . Why I’ve written “connected” because if we have something like  that

we should choose 6,1 but not 5,4 because sum 6+1 < 5+4. OK interesting observation… So, what will be if we start from bottom to top ? We can choose smallest number and all will be correct. That is good, but how to check “connection”. In this situation we can use rule from Dynamic Programming(DP) (Store sum under i position of i-element from next level and min from i and i+1 element from stored values.) OK, lets go …

What I’ve written :

Create cache (remember about DP)

Get last line(level) from triangle and put to cache

after that start from next level and

Store sum under i position of i-element from next level and min from i and i+1 element from stored values.

How this technique is working ? That is very easy, try to test our example :

  • firstly we have put last level to cache , so, cache contains next values

  • start loop from next level

i == 0, so, we store under 0-position  smallest sum  (6+4 or 6+1)

next positions the same, OK after second line we will have our cache like next

  • go to next level

cache will be next

  • go to next level

cache will be next

so, just return 0 position and that is all

So, we solved next task, that is good 🙂 Thanks!

READ  Compare Best HTML Parsers in Java

Leave a Reply

Your email address will not be published. Required fields are marked *