# leetcode: triangle

This is also a problem which can be easily solved by dynamic programming (DP is so ubiquitous). Anyway, The **Note** said

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.

Well, acctually the problem can be solved without extra space. The idea is quit simple:

We store the dp value (current minimum path sum) in-place from the bottom up, then the value in the tip of triangle is the result.

1 | class Solution { |