Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

178. Triangle

MediumDay 52 of 60Dynamic Programming

You are given a triangle as a list of rows, where row i has i + 1 numbers. Start at the top and move down one row at a time; from index j you may step to index j or j + 1 in the next row. Return the smallest possible sum of a path from the top to the bottom row.

Example 1
Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
The path 2, 3, 5, 1 sums to 11.
Example 2
Input: triangle = [[-10]]
Output: -10
Constraints
  • 1 <= triangle.length <= 200
  • triangle[i].length == i + 1
  • -10^4 <= triangle[i][j] <= 10^4
Hints
Frequently asked at: Amazon, Apple, Bloomberg
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min