C# - in place bottom up DP solution


  • 0
        public IList<int> GetRow(int rowIndex) 
        {
            int[] result = new int[rowIndex + 1];
            result[0] = 1;
            
            // bottom up dynamic programming, iterate up from row 1
            for (int row = 1; row < rowIndex + 1; row++)
            {
                // iterate over columns working from right to left
                // also stopping before last column, this will always remain 1
                // Note: you could iterate columns left to right but that would require use of temp int variable
                for (int column = rowIndex - 1; column > 0; column--)
                {
                    result[column] = result[column] + result[column-1];
                }
                
                // set right edge to 1
                result[rowIndex] = 1;
            }
            
            return new List<int>(result);
        }
    

Log in to reply
 

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