C# - DP/memorization - top down - not optimal but simple concept - accepted


  • 0
    public int MinimumTotal(IList<IList<int>> triangle) 
    {
        return Min(triangle, 0, 0, new Dictionary<Tuple<int,int>, int>());    
    }
    
    public int Min(IList<IList<int>> rows, int row, int col, Dictionary<Tuple<int,int>, int> map)
    {
        if (row >= rows.Count || col < 0 || col >= rows[row].Count) return int.MaxValue;
        if (row == rows.Count - 1) return rows[row][col];
        
        Tuple<int,int> key = new Tuple<int,int>(row, col);
        if (map.ContainsKey(key)) return map[key];
        
        int minRight = Min(rows, row + 1, col + 1, map);
        int minCenter = Min(rows, row + 1, col, map);
        
        int min = rows[row][col] + Math.Min(minRight, minCenter);
        map[key] = min;
        return min;
    }

Log in to reply
 

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