recursive C# solution using memoization (DP)


  • 0
    K
    public class Solution {
        public int MinimumTotal(IList<IList<int>> triangle) {
            int height = triangle.Count;
            int length = triangle[height-1].Count;
            int[,] grid = new int[height,length];
            int min = Int32.MaxValue;
            for (int i= 0;i<length;i++)
            {
                int sum = Sum(height-1,i,triangle,grid);
                if (sum < min) min = sum;
            }
            return min;
        }
        public int Sum(int x,int y, IList<IList<int>> triangle, int[,] grid)
        {
            if ( x==0 && y == 0)
                grid[x,y] = triangle[x][y];
            else if (y == 0)
                grid[x,y] = (grid[x-1,y] == 0 ? Sum(x-1,y,triangle,grid) : grid[x-1,y]) + triangle[x][y];
            else if (x == y)
                grid[x,y] = (grid[x-1,y-1] == 0 ? Sum(x-1,y-1,triangle,grid) : grid[x-1,y-1]) + triangle[x][y];            
            else
            {
                grid[x,y] = Math.Min((grid[x-1,y-1] == 0 ? Sum(x-1,y-1,triangle,grid) : grid[x-1,y-1]),
                                     (grid[x-1,y] == 0 ? Sum(x-1,y,triangle,grid) : grid[x-1,y]))
                            + triangle[x][y];
            }
            return grid[x,y];
        }
    }
    

Log in to reply
 

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