Triangle - Dynamic Programming

Problem is here: https://leetcode.com/problems/triangle/

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

Popular posts from this blog

Count Binary Substrings

Count Vowels Permutation: Standard DP

Maximum Number of Balloons