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

[crayon-5bf054fbcedf6902516776/] 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 onlyO(n) extra space, wherenis 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

[crayon-5bf054fbcee02543335544/]
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 …

[crayon-5bf054fbcee06002943179/]
What I’ve written :

Create cache (remember about DP)

[crayon-5bf054fbcee0b181972202/]
Get last line(level) from triangle and put to cache

[crayon-5bf054fbcee0f567447432/]
after that start from next level and

[crayon-5bf054fbcee13999639432/] How this technique is working ? That is very easy, try to test our example :Store sum under i position of i-element from next level and min from i and i+1 element from stored values.

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

- start loop from next level

[crayon-5bf054fbcee1d034811729/] next positions the same, OK after second line we will have our cache like next

[crayon-5bf054fbcee21901950415/]

- go to next level

[crayon-5bf054fbcee28296746687/]

- go to next level

[crayon-5bf054fbcee2e902459071/] so, just return 0 position and that is all

[crayon-5bf054fbcee32225199984/] So, we solved next task, that is good 🙂 Thanks!