LeetCode Q120 Triangle Dynamic Programming

Q120 Triangle




Solution

 level 1:    [2],
 level 2:   [3,4],      [3,4],
 level 3:  [6,5,7],  [7, 6, 10]
 level 4: [4,1,8,3]

 Think from bottom.
 When we at level 3,
 standing at 6, minimum total steps from bottom would be min(6 + 4, 6 + 1) = 7
 standing at 5, minimum total steps from bottom would be min(5 + 1, 5 + 8) = 6
 ...
 Thus, f[level][position] = f[level][position] + min(f[level + 1][position], [level + 1][position + 1])

 And we can just update the total steps from bottom in the array of the current level
 we can modify level 3 : [6,5,7],  -> [7, 6, 10]
 so we don't need any extra space at all.

https://github.com/Sylvia-YiyinShen/Algorithm/blob/master/DynamicProgramming/Q120Triangle.playground/Contents.swift