Share my simple DP solution


  • 0
    B

    Consider from bottom up, for the last layer i, each number j has two choices: add the previous number sum from layer [i-1][j], or [i-1][j-1], and we just need to select the smaller one.

     public int minimumTotal(IList<IList<int>> triangle)
            {
                var prevResults = new List<int>(){triangle[0][0]};
                List<int> currentResult = prevResults;
    
                for (int i = 1; i < triangle.Count; i++)
                {
                    currentResult = new List<int>();
                    for (int j = 0; j < triangle[i].Count; j++)
                    {
                        int prev = int.MaxValue;
                        if (j - 1 > -1)
                        {
                            prev = Math.Min(prev,prevResults[j - 1]);
                        }
                        if (triangle[i-1].Count > j)
                        {
                            prev = Math.Min(prev,prevResults[j]);
                        }
                        currentResult.Add(triangle[i][j]+prev);
                    }
                    prevResults = currentResult;
                }
                return currentResult.Min();
            }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.