C, Bottom up, No Extra Space, Heap Analogy


  • 1
    M

    Once we visualize the triangle as a heap, the bottom up approach is easy to understand . We need to essentially allow the smaller values to rise to the top. Let's implement this in-place by utilizing the same triangle array.

    Both iterative and recursive solutions are given below:

    int minimumTotal(int** tr, int tRow, int *tColSizes)
    {
        int j, i;
         for (i = tRow - 2; i >= 0; --i) // upper row selector
            for (j = 0; j < tColSizes[i]; ++j) // pick smaller sums
                (tr[i])[j] += (tr[i + 1])[j] > (tr[i + 1])[j + 1] ?
                              (tr[i + 1])[j + 1] : (tr[i + 1])[j];
        return (tr[0])[0];
    }
    

    Same algorithm, but recursive.

    int minimumTotal(int** tr, int tRow, int *tColSizes)
    {
        int j, row = tRow - 2;
        for (j = 0; row >= 0 && j < tColSizes[row]; ++j)
                (tr[row])[j] += (tr[row + 1])[j] > (tr[row + 1])[j + 1] ?
                                 (tr[row + 1])[j + 1] : (tr[row + 1])[j];
        /* Stop recursion when rows < 2 */
        return (tRow <= 2) ? **tr : minimumTotal(tr, tRow - 1, tColSizes);
    }
    

  • 0
    Y

    Bottom up is a great idea


Log in to reply
 

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