Simple Recursive Solution : C#


  • 0
    S
    public class Solution {
        IList<IList<int>> triangle = null;
        Dictionary<Index, int> dp = new Dictionary<Index, int>();
        
        class Index
        {
            public int i, j;
            public Index(int x, int y)
            {
                i = x;
                j = y;
            }
            
            public override int GetHashCode()
            {
                return i+j;
            }
            
            public override bool Equals(object o)
            {
                return (((Index)o).i == i && ((Index)o).j == j);
            }
        }
        
        public int MinimumTotal(IList<IList<int>> triangle) {
            this.triangle = triangle;
            return Helper(0, 0);
        }
        
        int Helper(int row, int col)
        {
            // base case
            if(row == triangle.Count - 1)
            {
                return triangle[row][col];
            }
            
            // Memoize
            Index i = new Index(row, col);
            if(dp.ContainsKey(i))
            {
                return dp[i];    
            }
            
            // recurrence
            dp[i] = Math.Min(Helper(row+1, col), Helper(row+1, col+1)) + triangle[row][col];
            return dp[i];
        }
    }
    

Log in to reply
 

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