Triangle - Dynamic Programming
Problem is here: https://leetcode.com/problems/triangle/
In 2020 it would be the 100th birthday for Richard Bellman, the inventor of Dynamic Programming - Happy BDay, Sir!!! ACC.
public class Solution
{
public int MinimumTotal(IList<IList<int>> triangle)
{
int[] previousMin = new int[triangle.Count];
int[] currentMin = new int[triangle.Count];
int rowIndex = 0;
foreach (List<int> row in triangle)
{
if (rowIndex == 0)
{
previousMin[rowIndex] = row[0];
currentMin[rowIndex] = row[0];
}
else
{
for (int i = 0; i < row.Count; i++)
{
if (i == 0)
{
currentMin[i] = previousMin[i] + row[i];
}
else if (i == row.Count - 1)
{
currentMin[i] = previousMin[i - 1] + row[i];
}
else
{
currentMin[i] = row[i] + Math.Min(previousMin[i - 1], previousMin[i]);
}
}
}
previousMin = (int[])currentMin.Clone();
rowIndex++;
}
return currentMin.Min();
}
}
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
[ [2], [3,4], [6,5,7], [4,1,8,3] ]
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.
Traditional DP problem: keep a track of the min sum for each position from [0..n-1]. You actually use 2*n space for previous and current, swapping them along the way. Code is below.In 2020 it would be the 100th birthday for Richard Bellman, the inventor of Dynamic Programming - Happy BDay, Sir!!! ACC.
public class Solution
{
public int MinimumTotal(IList<IList<int>> triangle)
{
int[] previousMin = new int[triangle.Count];
int[] currentMin = new int[triangle.Count];
int rowIndex = 0;
foreach (List<int> row in triangle)
{
if (rowIndex == 0)
{
previousMin[rowIndex] = row[0];
currentMin[rowIndex] = row[0];
}
else
{
for (int i = 0; i < row.Count; i++)
{
if (i == 0)
{
currentMin[i] = previousMin[i] + row[i];
}
else if (i == row.Count - 1)
{
currentMin[i] = previousMin[i - 1] + row[i];
}
else
{
currentMin[i] = row[i] + Math.Min(previousMin[i - 1], previousMin[i]);
}
}
}
previousMin = (int[])currentMin.Clone();
rowIndex++;
}
return currentMin.Min();
}
}
Comments
Post a Comment
[γγ¬γΌγ ]