Leetcode.com problem 120: "Triangle"
James S. Plank
Thu Jun 16 11:20:17 AM EDT 2022
This is a nice and straightforward Dynamic Programming problem. One of the
things I like about it is that "step 4" of dynamic programming,
as described in the CS302 Lecture Notes on Dynamic Programming
answers the "follow up" question on the Leetcode writeup.
Let's walk through the four steps:
Step 1: Spot the recursion
Let's suppose you want to find the answer for
triangle[i][j]. If i is the last row of triangle,
then you're done -- the answer is triangle[i][j].
If i is not the last row, then you recursively solve
the problem on
triangle[i+1][j] and
triangle[i+1][j+1]. Fortunately, because of the "triangle" nature
of the vector, you are guaranteed that both of these always exist.
You add the minimum of your recursive calls, add it to triangle[i][j],
and that's your answer. Easy enough.
Code for this answer is in
step-1.cpp.
Step 2: Memoize
If you submit your step 1 answer, you'll fail with a "Time Limit
Exceeded", because your calls will exponentially
blow up. Add a cache. My cash was a vector of vectors just like
triangle. One challenge is what to put into the cache
to denote an empty entry? -1 won't do, because that's a legal
value for your answer. Look at the problem's constraints -- values
in triangle are between -10,000 and 10,000 and the maximum
size of triangle is 200. So any answer will be between -200*10,000 and 200*10,000. Simply choose your "empty" value to be an integer outside
that range.
This implementation works and is "accepted" by leetcode, but you can
do better from a time and space perspective. The leetcode evaluation
for this answer was that it was faster than only 5.68% of
C++ implementations, and smaller than only 34.40%.
Code for this answer is in
step-2.cpp.
Step 3: Remove the recursion
Since your recursion always goes to higher values of i,
you remove the recursion by calculating the cache, starting with the
highest value of i and decrementing. When I submitted
that to leetcode, it sped me up so that I was faster than 33.91%
of C++ answers, but it used more space. Why more space? Probably
because I'm calling push_back() to create my cache instead of
resizing.
Code for this answer is in
step-3.cpp.
Step 4: Reduce the size of the cache
When you look at your solution for step 3, you'll notice that you only
ever use two rows of the cache, so you can reduce the cache size to
two rows, and use modular arithmetic (always take i or i+1
mod 2).
Can you do better? Yes! When you're calculating cache[i][j],
you'll note that you need cache[i+1][j] and
cache[i+1][j+1]. When you're done, you won't ever need
cache[i+1][j] again. That means that you only need one row
in your cache!
If this were an interview question, you'll note that both the one-row
and the two-row solutions are valid answers to the "follow up". Both
caches are O(n) -- remember that 2n is O(n).
In the code below, I don't bother with a separate cache -- I simply
use the last row of triangle, so there should be almost no extra
space requirement! Yep -- faster than 56% and smaller than 98.37%!
Code for this answer is in
step-4.cpp.