Tags: %TAGME{ tpaction="" web="Main" tag="" }% view all tags

LeetCode Exercise 9

Dynamic Programming
Due: Nov 18, 11:55 pm

Moodle Link

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.
Topic revision: r1 - 2016-11-11 - JimSkon
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback