LeetCode Exercise 9

Dynamic Programming
Due: April 24, 9:00am

Moodle Link


Group 1 Preston, Kyle, Thomas
Group 2 John, Flynn
Group 3 Isaac, Boning
120. Triangle120

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.

You are to find a dynamic programming solution to this problem, and implement it on Leetcode.


Turn in:

  1. Source code for your solution
  2. Samples runs showing the operation with input and outputs.
  3. An explanation of how this problem includes the concept of an optimal substructure.
  4. A complete runtime asymptotic analysis.

Be prepared to discuss you solutions in class.

Edit | Attach | Watch | Print version | History: r4 < r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r4 - 2019-04-21 - JimSkon
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback